0

So let's say we bitshift 1 by some number x; eg, in c:

unsigned char cNum= 1, x= 6;

cNum <<= x;

cNum will equal 01000000b (0x40).

Easy peasy. But without using a lookup table or while loop, is there a simple operation that will take cNum and give me x back?

Jim C
  • 165
  • 8
  • What you want to do is count leading zeros, or find first bit set. Some platforms have instructions that can do this, and some languages have easy ways to use those instructions. You give C as an example, but don't make it clear whether you're looking for a generic mathematical approach, or a specific language implementation. – Thomas Jager May 22 '21 at 14:43
  • I'll be using c to implement the answer, but if someone were to explain an elegant way finding x using simple maths, that would be fine. – Jim C May 22 '21 at 15:06
  • There is no standard way in C to do in one quick way. POSIX adds `ffs`, GCC adds intrinsics, and a good compiler can even detect a manual loop and optimize it out with the right instruction. – Thomas Jager May 22 '21 at 15:27
  • I've revised the title, as I really only want the simplest way to get the index of a bit in a bitmap with only one bit set. log2() will do this but requires a floating point number; I'd prefer to do it with an integer. – Jim C May 22 '21 at 15:30
  • If you want standard C, the best way would be to look at the answers in this C++ question: https://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c. – Thomas Jager May 22 '21 at 15:33
  • `1 << 6 == 2 << 5 == 0x40` so the shift is not uniquely determined if you only know the final value. – dxiv May 22 '21 at 22:49
  • https://graphics.stanford.edu/~seander/bithacks.html – tehtmi May 23 '21 at 04:07
  • See my answer below. The question is how much 1 has been bitshifted, not any random bit. – Jim C May 23 '21 at 23:07

2 Answers2

0

AFAIK, no 'simple' formula is available.

One can, however, calculate the index of most significant (or least significant) set bit:

 a = 000010010, a_left = 3, a_right = 1
 b = 001001000, b_left = 5, b_right = 3

The difference of the shifts is 2 (or -2).

One can then shift the smaller by abs(shift) to compare that a << 2 == b. (In some architectures there exists a shift by signed value, which works without absolute value or checking which way the shift needs to be carried.)

In ARM Neon there exists an instruction for counting the MSB bit and in Intel there exists an instruction to scan both from left and right.

Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
0

log2(cNum)+ 1; will yield x where cNum != 0, at least in GNU c.

And the compiler does the casts automagically which is probably bad form, but it gives me what I need.

Jim C
  • 165
  • 8