Number of unset bit left of most significant set b

Question

Assuming the 64bit integer 0x000000000000FFFF which would be represented as

00000000 00000000  00000000 00000000
00000000 00000000 >11111111 11111111

How do I find the amount of unset bits to the left of the most significant set bit (the one marked with >) ?

Answer 1

Try

int countBits(int value)
{
    int result = sizeof(value) * CHAR_BITS;  // should be 64

    while(value != 0)
    {
        --result;
        value = value >> 1; // Remove bottom bits until all 1 are gone.
    }
    return result;
}

Answer 2

Use log base 2 to get you the most significant digit which is 1.

log(2) = 1, meaning 0b10 -> 1
log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2
log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3
log(16) = 4 you get the idea

and so on... The numbers in between become fractions of the log result. So typecasting the value to an int gives you the most significant digit.

Once you get this number, say b, the simple 64 - n will be the answer.

function get_pos_msd(int n){
    return int(log2(n))
}

last_zero = 64 - get_pos_msd(n)

Answer 3

In straight C (long long are 64 bit on my setup), taken from similar Java implementations: (updated after a little more reading on Hamming weight)

A little more explanation: The top part just sets all bit to the right of the most significant 1, and then negates it. (i.e. all the 0's to the 'left' of the most significant 1 are now 1's and everything else is 0).

Then I used a Hamming Weight implementation to count the bits.

unsigned long long i = 0x0000000000000000LLU;

i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i |= i >> 32;
// Highest bit in input and all lower bits are now set. Invert to set the bits to count.
i=~i;

i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count
i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count
i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count 
i *= 0x0101010101010101LLU; // add each byte to all the bytes above it
i >>= 56; // the number of bits

printf("Leading 0's = %lld\n", i);

I'd be curious to see how this was efficiency wise. Tested it with several values though and it seems to work.

Answer 4

Here you go, pretty trivial to update as you need for other sizes...

int bits_left(unsigned long long value)
{
  static unsigned long long mask = 0x8000000000000000;
  int c = 64;
  // doh
  if (value == 0)
    return c;

  // check byte by byte to see what has been set
  if (value & 0xFF00000000000000)
    c = 0;
  else if (value & 0x00FF000000000000)
    c = 8;
  else if (value & 0x0000FF0000000000)
    c = 16;
  else if (value & 0x000000FF00000000)
    c = 24;
  else if (value & 0x00000000FF000000)
    c = 32;
  else if (value & 0x0000000000FF0000)
    c = 40;
  else if (value & 0x000000000000FF00)
    c = 48;
  else if (value & 0x00000000000000FF)
    c = 56;

  // skip
  value <<= c;

  while(!(value & mask))
  {
    value <<= 1;
    c++;
  }

  return c;
}