从二进制数中提取奇数位的最佳方法

Question

给定一个 64 位数字，我需要从中提取每一位，并将其转换为数字：

decimal:  357
binary:   0000 0001 0110 0101
odd bits:  0 0  0 1  1 0  1 1
decimal:  27

有什么好的算法可以做到这一点吗？不，不是硬件，这是用于现实世界的:)

Answer 1

创建一个包含 256 个条目的 table 来查找每个字节。 table 中的一个条目的值将被转换为数字的东西。然后将 4 个字节与移位一起粘贴以得出最终数字。

这里有一个缩小比例的例子，这样你就明白了。查找部分使用 4 位而不是 8 位：

向上看说 01010010。分成 0101 和 0010。向上看我们得到 11、00和粘贴在一起：1100

table 为 256，您将需要 8 次查找和相应的粘贴。如果您有 2**16 个条目的内存，那么您只需要进行四次查找，并且粘贴也按比例减少。

table 不必是二的偶数次方。例如，对于 1024 个条目 (2**10)，有 7 次查找。当 table 指数恰好是 2 的幂（2、4、8、16 或 32）时，就存在经济。

Answer 2

我会一次执行两个算术右移（直到二进制数的长度）。这个>>用在我的逻辑中是为了算术移位。

(Note: In C language, right shifts may or may not be arithmetic!)

喜欢，

int count=0;
bit=extractLastbit(binary_representation_of_the_number);

while(count!=binaryLength){
  // binaryLength is the length of the binary_representation_of_the_number
  binary_representation_of_the_number=binary_representation_of_the_number>>2;

  bit.appendLeft(extractLastbit(binary_representation_of_the_number);
  count=count+2;
}

其中，

extractLastBit()提取二进制数的LSB； appendLeft() 将新提取的位移到旧位的左侧。

Answer 3

参见How to de-interleave bits (UnMortonizing?)。

x = x& 0x5555555555555555; //restrict to odd bits.
x = (x | (x >> 1)) & 0x3333333333333333;
x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff0000ffff;
x = (x | (x >>16)) & 0x00000000ffffffff;

Answer 4

这是我最终想出的 - 每个奇数位都是 from/to X 值，每个偶数位 - from/to Y。我不得不把它写成 JavaScript。

function xyToIndex(x, y) {
    // Convert x,y into a single integer with alternating bits
    var mult = 1, result = 0;
    while (x || y) {
        result += (mult * (x % 2));
        x = Math.floor(x / 2);
        mult *= 2;
        result += (mult * (y % 2));
        y = Math.floor(y / 2);
        mult *= 2;
    }
    return result;
}

function indexToXY(index) {
    // Convert a single integer into the x,y coordinates
    // Given a 64bit integer, extract every odd/even bit into two 32bit values
    var x = 0, y = 0, mult = 1;
    while (index) {
        x += mult * (index % 2);
        index = Math.floor(index / 2);
        y += mult * (index % 2);
        index = Math.floor(index / 2);
        mult *= 2;
    }
    return [x, y];
}

从二进制数中提取奇数位的最佳方法

Best way to extract ODD digits from a binary number

algorithm

bit-manipulation