Search code examples
algorithmbinarypseudocode

Binary number with two one insite it

is there an algorithm that find all binaries numbers between a and b, in which there are exactly two one? For example:

a = 5
b = 10
find(a, b)

It will find

5 = 00000101
6 = 00000110
9 = 00001001
10 = 00001010
Solution

  • A bit-hacking trick that iterates through all bit-paterns that contain the same number of 1-bits looks as follows

    unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v + (((v ^ x) / u) >> 2);
  return x;
}

    It generates the values in ascending order. It takes the previous value and transforms it into the next one with the same number of 1-bits. This means that you just have to start from the minimal bit combination that is greater or equal to a and iterate until you encounter a value greater than b.

    Of course, in this form it will only work if your a and b are within the range of unsigned.