How to determine the number of similar bits?

Question

I need to compare two numbers and look for similarities in more significant bits. I'm trying to determine the number of least significant bits that differ.

10111000
10111011

184 and 187 require an offset of two, because only two least significant bits differ.

10111011
11111011

187 and 251 require an offset of seven, because the seventh least significant bit differs.

My first idea was to XOR the numbers together, then bit-shift right until the number equaled zero. I feel like there is a better bit-wise solution to this that doesn't involve loops, but I haven't done enough bit-twiddling of my own to come up with it.

The solution needs to work for any 64 bits, as my numbers are being stored as UInt64. This is being written in C#, but the solution is most likely a language agnostic one.

---

11101101
11010101

Would need an offset of 6 bits. I'm trying to find how many similar bits I can take off the top.

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;
}

I think this implements your algorithm and it's very fast, needing only 6 steps. See this great source of bit twiddling hacks.

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