如何确定相似位数？

Question

我需要比较两个数字,并在更重要的位中寻找相似之处.我正在尝试确定不同的最低有效位数.

10111000
10111011

184和187要求偏移量为2,因为只有两个最低有效位不同.

10111011
11111011

187和251要求偏移量为7,因为第七个最低有效位不同.

我的第一个想法是将数字异或,然后向右移位直到数字等于零.我觉得有一个更好的逐位解决方案,这不涉及循环,但我没有做足够的钻孔我自己提出它.

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

---

11101101
11010101

需要6位的偏移量.我试图找到多少相似的位,我可以脱颖而出.

Answer 1

#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