The number of bits cleared to the left of the most significant bit?

Question

Assuming a 64-bit integer 0x000000000000FFFF to be represented as

 00000000 00000000 00000000 00000000 00000000 00000000 >11111111 11111111 

How to find the number of canceled bits to the left of the most significant bit of the set (the one marked with>)?

Answer 1

 // clear all bits except the lowest set bit x &= -x; // if x==0, add 0, otherwise add x - 1. // This sets all bits below the one set above to 1. x+= (-(x==0))&(x - 1); return 64 - count_bits_set(x); 

Where count_bits_set is the fastest version of the counting bits you can find. See https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel for different methods of counting bits.

Answer 2

In direct C (long, long, 64 bits in my setup), taken from similar Java implementations: (updated after a bit more reading on the Hamming weight)

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

Then I used Hamming Weight 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 = %lld\n", i); 

I would be interested to see how effective it was. Tested it with multiple values, although it seems to work.

Answer 3

Based on: http://www.hackersdelight.org/HDcode/nlz.c.txt

 template<typename T> int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return cv;} 

If you need a version that allows you to dine, here you are:

 int clz(uint64_t v) { int n=64,c=64; while (n) { n>>=1; if (v>>n) c-=n,v>>=n; } return cv; } 

As you will see, you can save on cycles by carefully analyzing the assembler, but the strategy here is not terrible. The while loop will run Lg [64] = 6 times; each time it converts a problem into one of counting the number of leading bits per integer twice. The if statement inside the while loop asks the question: “can I imagine this integer twice as many bits” or similarly “if I cut it in half, I lost it?”. After the if () payload is completed, our number will always be in the lower n bits. At the final stage, v is either 0 or 1, and this completes the calculation correctly.

Answer 4

If you are dealing with integer integers, you can do this:

 #include <math.h> int numunset(uint64_t number) { int nbits = sizeof(uint64_t)*8; if(number == 0) return nbits; int first_set = floor(log2(number)); return nbits - first_set - 1; } 

I do not know how this will be compared in performance with the loop and count methods that have already been proposed, since log2 () can be expensive.

Edit

This can cause some problems with high-value integers, since the log2() function distinguishes double , and some numerical problems may occur. You can use the log2l() function, which works with long double . A better solution would be to use the integer function log2() , as in this question .

Answer 5

I am not sure I understood the problem correctly. I think you have a 64-bit value and you want to find the number of leading zeros in it.

One way is to find the most significant bit and simply subtract its position from 63 (assuming the least significant bit is bit 0). You can find out the most significant bit by checking if the bit from the loop is set for all 64 bits.

Another way could be to use (non-standard) __builtin_clz in gcc.

Answer 6

Same idea as user470379's , but countdown ...
Suppose all 64 bits are not set. While the value is greater than 0, shift the value to the right and decrease the number of bits canceled:

 /* untested */ int countunsetbits(uint64_t val) { int x = 64; while (val) { x--; val >>= 1; } return x; } 

Answer 7

I agree with the idea of ​​binary search. However, two points are important here:

• The range of valid answers to your question is from 0 to 64 inclusive . In other words, there may be 65 different answers to the question. I think (almost certainly) everyone who posted the binary search solution missed this point, so they will get the wrong answer for zero or a number with an MSB bit.
• If the speed is critical, you can avoid the cycle. There's an elegant way to achieve this with templates.

The following template material correctly finds the MSB of any unsigned type variable.

 // helper template <int bits, typename T> bool IsBitReached(T x) { const T cmp = T(1) << (bits ? (bits-1) : 0); return (x >= cmp); } template <int bits, typename T> int FindMsbInternal(T x) { if (!bits) return 0; int ret; if (IsBitReached<bits>(x)) { ret = bits; x >>= bits; } else ret = 0; return ret + FindMsbInternal<bits/2, T>(x); } // Main routine template <typename T> int FindMsb(T x) { const int bits = sizeof(T) * 8; if (IsBitReached<bits>(x)) return bits; return FindMsbInternal<bits/2>(x); } 

Answer 8

Here you go, it is 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; } 

Answer 9

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 10

Use database 2 to get 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 between them become fractions of the result of the magazine. So casting a value to int gives you the most significant digit.

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

 function get_pos_msd(int n){ return int(log2(n)) } last_zero = 64 - get_pos_msd(n)