异或距离练习

使用异或和位运算的 Rust 异或距离练习

包	文档	Travis CI	CodeCov

概述

为了更好地了解 异或运算 和 异或距离，您可以尝试以下练习，该练习在下面的 挑战 部分中描述。它基于我在面试中收到的挑战。

“xor-distance-exercise” 包本身是针对该挑战的通用解决方案。数据文件夹包含接受挑战的起点，所以如果您打算自己找到/实现解决方案，请不要偷看任何其他地方。

挑战

居住在异或空间的人们经历了不同的物理定律。空间中的地点不是由位置坐标指定，而是由一个无符号的 64-bit 整数指定。两点 x 和 y 之间的距离不是您在我们三个线性空间中习惯的距离，您必须对两个位置的位异或 x ^ y 进行计算以获得它们的异或空间距离。

在异或空间中也有企业家，其中一位提出了一个本地新鲜食品配送系统的想法

pub struct FoodDeliverySystem {
    addresses: Vec<u64>,
}

这个想法导致了一个应用程序的创建。您输入您的 位置 和您想要从最近的农场获取食品的 数量。它计算从最近的农场到第 n-th 个最近的农场的地址，按从最近到最远的顺序排列

    pub fn closest_farms(&self, position: u64, count: usize) -> Vec<u64> {
        let mut sorted_farms = self.addresses.clone();
        sorted_farms.sort_by_key(|address| *address ^ position);
        sorted_farms.truncate(count);
        sorted_farms
    }

这些信息将交给配送司机和农民，以便司机可以从最远的农场到最近的农场取货，以最大限度地保证食品的新鲜度。

然而，农民很好奇，他们想知道谁是他们的客户。他们要求您编写一个比 O(n2) 更好的高效函数（他们喜欢经济实惠），该函数给定一个有序的最近农场地址序列（从最近到第 n-th 个最近），返回一个可能的 位置。可能存在多个这样的 位置，但只需返回其中一个即可。如果没有这样的 位置，则应返回 None

    pub fn reverse_closest_farms(&self, closest_farms: &[u64]) -> Option<u64> {
        // TODO: This is the part of an exercise you should implement.
        None
    }