-4

I'm looking for an efficient method (preferably using few bitwise operations) that returns the count of left shifts or solve the equation as:

find x for a given y where y=2^x

For example (1 << 4) = 16 = 10000b. So if 16 is given how can I solve it for the amount of left shift which is 4 in given case. Also, I'm not looking for a method that involves loop or log method like:

unsigned int count_shift(unsigned int shifted)
{
    unsigned int count = 0;

    for (count = 0; shifted != 0x1; count++)
    {
        shifted /= 2;   
    }
    return count;
}

Cheers!

Sajjad Ahmad
  • 421
  • 6
  • 13
  • 1
    [Fast computing of log2 for 64-bit integers](https://stackoverflow.com/q/11376288/995714) – phuclv Sep 26 '17 at 15:02
  • @LưuVĩnhPhúc Bit-Twiddling Hacks FTW. – Persixty Sep 26 '17 at 15:05
  • @LưuVĩnhPhúc my question is about **efficient method in C** – Sajjad Ahmad Sep 26 '17 at 15:08
  • 2
    Efficient on memory space, or register usage? – Martin James Sep 26 '17 at 15:17
  • 1
    You may have been put off by the C# reference. But the second link from @LưuVĩnhPhúc leads to a nice and very compact answer in C: https://stackoverflow.com/a/24748784/4213662 – Persixty Sep 26 '17 at 15:17
  • @LưuVĩnhPhúc Even though OP's code does the same thing as the linked question, I think the question you linked is more general than OP's, because he says that the parameter is going to be 2^x. – Sergey Kalinichenko Sep 26 '17 at 15:17
  • 2
    @MartinJames for fewer CPU cycles as the code implements ISR (interrupt service routine) on an embedded platform – Sajjad Ahmad Sep 26 '17 at 15:21
  • @SajjadAhmed OK It's somewhat annoying that there is no simple way to do this:( – Martin James Sep 26 '17 at 15:22
  • @MartinJames: I don't think it comes up that often, to be honest. You can hump it out in a handful of lines of assembler. – Bathsheba Sep 26 '17 at 15:23
  • 2
    @Bathsheba that's what I would do in an interrupt-handler, yes. I guess you could quickly find out which byte has the one in it and then lookup, or just rotate through carry. – Martin James Sep 26 '17 at 15:26
  • 1
    @MartinJames There are some CPUs having special instructions, like ARMs CLZ (count leading zeros). One can even attempt to use `__builtin_clz` – Eugene Sh. Sep 26 '17 at 15:37
  • @EugeneSh. Your answer is most relevant to the question. I'll post the implementation with its efficiency superiority. – Sajjad Ahmad Sep 26 '17 at 15:55
  • Not a serious answer, but it would work: You could cast the `unsigned int` to a `float`, then coerce it back to `uint32_t` using a union or pointer trickery. Bits [30:23] are an offset logarithm. With some FP hardware it might be fast. – NickJH Sep 26 '17 at 16:14
  • To all folks who don't know the answer and just relied on downvoting. Here is the efficient way – Sajjad Ahmad Sep 26 '17 at 16:22
  • 1
    `unsigned int shift_count(unsigned int shifted) { return (31 - __builtin_clz(shifted)); }` it uses architecture's (tested on ARM-Cortex-A7 and Intel x64) **clz** instruction to calculate the leading zeros. It takes 4 cycles on the ARM and 3 cycles on x64 to calculate the log. So if you subtract it from the total bits of the input register (31 - 0) it will return you the location of the high bit. – Sajjad Ahmad Sep 26 '17 at 16:33
  • @SajjadAhmed Nice answer. If you are able to be platform tied best to put that in the question. Might not get closed as a duplicate then. Though people are a bit keen IMHO to match with similar but not same questions. – Persixty Sep 26 '17 at 17:22
  • "I'm looking for an efficient method" (speed) is a reasonable goal. Adding "not looking for a method that involves loop or log" is an unnecessary limitation. For a good way to find a fast solution, next time, post test code to assess how you rate performance. – chux - Reinstate Monica Sep 26 '17 at 18:19

2 Answers2

1

If the number is guaranteed to be a power of two, i.e. y == 1 << x, you can do it with a 256-byte look-up table and four look-ups:

static unsigned char lookup[256] = {
    [0x01]=1, [0x02]=2, [0x04]=3, [0x08]=4, [0x10]=5, [0x20]=6, [0x40]=7, [0x80]=8
};

unsigned log2uint(unsigned y) {
    unsigned res = lookup[(y >>  0) & 0xFF];
    if (res) return res +  0 - 1;
    res = lookup[(y >>  8) & 0xFF];
    if (res) return res +  8 - 1;
    res = lookup[(y >> 16) & 0xFF];
    if (res) return res + 16 - 1;
    res = lookup[(y >> 24) & 0xFF];
    if (res) return res + 24 - 1;
    return 0;
}

Demo 1

If you do not mind vendor-specific functionality, gcc provides __builtin_ctz function that returns the number of trailing zeros, which matches the return value that you get when y == 1 << x (Demo 2)

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
0

Unless you use a lookup table1, the fastest known way is O(N):

unsigned int count = 0;
while (shifted >>= 1){
  ++count;
}

1Which is how exp and log are evaluated on some chips - Newton Raphson-type algorithms with lookup tables defining certain function points.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483