如何确定相似位数的数量？

Question

我需要比较两个数字并查找更重要的位中的相似之处。我试图确定不同的最低有效位数。

10111000
10111011

由于只有两个最低有效位不同，因此184和187需要偏移量为二。

10111011
11111011

187和251需要偏移七位，因为第七位最不重要的位不同。

我的第一个想法是将这些数字进行异或运算，然后进行位移，直到数字等于零。我感觉有更好的位操作解决方案，不涉及循环，但我自己还没有进行足够的位操作来想出它。

该解决方案需要适用于任何64位，因为我的数字被存储为UInt64。这是用C#编写的，但解决方案很可能是一种语言无关的。

---

11101101
11010101

需要一个偏移量为6位。我试图找出可以从顶部取下多少相似的位。

- dlras2

---

这是一个不错的问题需要解决，但是如果出现例如11101101和11010101这样的数字（即多个位置存在差异），结果应该是什么并不十分清晰。 - Eugene Mayevski 'Callback

在循环中，通过移位1次，您甚至不需要对它们进行异或操作-而不是将其与0进行比较，您可以一直移位直到它们相等。 - mip

@Eugene - 我添加了你的例子。@doc - 是的，但这仍然是我想要避免的。我只是知道异或是正确的方向。 - dlras2

有趣的是，在x86汇编中，使用XOR的方法编码非常有效，几乎无法被攻击（除非引入特殊命令，如“获取字节中1的位置”），而在C#中，可能需要更多的代码。 - Eugene Mayevski 'Callback

@Eugene：我不确定你括号里的部分是什么意思。在x86汇编中，如果我们需要至少386，那么问题将简化为“xor”+“bsr”，对吧？而从Pentium II开始，这应该只需要很少量的时钟周期。 - Christopher Creutzig

@Christopher Creutzig，就是这样，我承认错误。谢谢你的指点。 - Eugene Mayevski 'Callback

Answer 1

听起来你已经发现了主要的技巧；r = x XOR y，然后找到 r 中最高位。有很多不同的方法可以解决这个问题。最快的方法是通过将 r 分成两半并检查上半部分是否为零来进行 O(n) 次操作。如果你在固定位数（你说是 64）上进行此操作，则展开循环以获得一系列测试：

pos = 0
r = x XOR y
if r>>32 == 0 :
   r = r & 2^32-1
else
   pos += 32
   r = r>>32
if r>>16 == 0 :
   r = r & 2^16-1
else
   pos += 16
   r = r>16
... etc

- Andrew

Answer 2

#include <stdio.h>
#include <stdlib.h>

#define TO_L(s) (strtol((s), NULL, 16))

int tsb(unsigned long xa, unsigned long xb) {
  unsigned long v = xa ^ xb;
  static const unsigned long b[] = {
    0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000L, 0xFFFFffff00000000L
  };
  static const unsigned int S[]  = { 1, 2, 4, 8, 16, 32 };
  unsigned int r = 0;

#define STEP(i)   \
  if(v & b[i]) {  \
    int t = S[i]; \
    v >>= t;      \
    r  |= t;      \
  }
  STEP(5)
  STEP(4)
  STEP(3)
  STEP(2)
  STEP(1)
  STEP(0)
  return r;
}

int main(int ac, char **av) {
  return printf("%d\n", tsb(TO_L(av[1]), TO_L(av[2]))), 0;
}

我认为这个实现了你的算法，并且非常快，只需要6步。请参见这个位操作技巧的绝佳源泉。

so ross$ ./a.out 1f f
4
so ross$ ./a.out 471234abcdabcd 981234abcdabcd
55
so ross$ ./a.out 1deadbeef 7feedface
34

- DigitalRoss

Answer 3

你可以很容易地编写一个O(log(n))的循环来查找最高位设置：

int findHighestSetBit(unsigned long long x) {
    int rv = 0;
    if (x == 0)
        return -1;  // no set bits
    for (int shift = 32; shift > 0; shift >>= 1) {
        if (x >> shift) {
            rv += shift;
            x >>= shift;
        }
    }
    return rv+1; // number least significant bit as '1' rather than '0'
}

如果速度太慢，您可以手动展开循环5次。

- Chris Dodd

Answer 4

假设首先你必须对8位数字进行操作。 最快的方法是使用256字节的查找表和预编译的值：

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed

unsigned diff = (unsigned)a ^ (unsigned)b; // sure you need XOR and not MINUS?
unsigned highest_bit_num = highest_bit_num_LUT[diff & 0xff];

现在将其扩展到更高的位数：

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed
unsigned diff = (unsigned)a ^ (unsigned)b; // sure you need XOR and not MINUS?
unsigned highest_bit_num = 0;
for (int i = 7; i >= 0; i--)    
    if (diff >> ( i*8) ){ // found most significant non-zero byte
        highest_bit_num = i*8 + highest_bit_num_LUT[diff >> (i*8)];
        break;
    }

现在我们最多只有8次迭代。

编辑：对于前3次迭代，使用DigitalRoss的想法会更快，然后再使用LUT。

- ruslik

Answer 5

类似于

floor( log(184 ^ 187) / log(2) ) + 1

没有循环，但可能不会更快，因为登录是一项昂贵的操作。你应该测试它，并与使用位移的简单循环进行比较。

有时（精心编码的）循环比无循环更快，特别是如果你最多只有64次迭代，而且通常还要少得多。

---

我的代码的更高效版本：

预先计算

double Ilog2 = 1 / log(2);

然后每次你需要它

floor( log(184 ^ 187) * ILog2 ) + 1

- Loïc Février