2

Here's a tough one(atleast i had a hard time :P):

find the index of the highest bit set of a 32-bit number without using any loops.

7

11 Answers 11

6

Very interesting question, I will provide you an answer with benchmark


Solution using a loop

uint8_t highestBitIndex( uint32_t n )
{
    uint8_t r = 0;
    while ( n >>= 1 )
        r++;
    return r;
}

This help to better understand the question but is highly inefficient.


Solution using log

This approach can also be summarize by the log method

uint8_t highestSetBitIndex2(uint32_t n) {
    return (uint8_t)(log(n) / log(2));
}

However it is also inefficient (even more than above one, see benchmark)


Solution using built-in instruction

uint8_t highestBitIndex3( uint32_t n )
{
    return 31 - __builtin_clz(n);
}

This solution, while very efficient, suffer from the fact that it only work with specific compilers (gcc and clang will do) and on specific platforms.

NB: It is 31 and not 32 if we want the index


Solution with intrinsic

#include <x86intrin.h> 

uint8_t highestSetBitIndex5(uint32_t n)
{
    return _bit_scan_reverse(n); // undefined behavior if n == 0
}

This will call the bsr instruction at assembly level


Solution using inline assembly

LZCNT and BSR can be summarize in assembly with the below functions:

uint8_t highestSetBitIndex4(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(
        .intel_syntax noprefix
            bsr eax, edi
        .att_syntax noprefix
        )"
            );
}

uint8_t highestSetBitIndex7(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(.intel_syntax noprefix
        lzcnt ecx, edi
        mov eax, 31
        sub eax, ecx
        .att_syntax noprefix
    )");
}

NB: Do Not Use unless you know what you are doing


Solution using lookup table and magic number multiplication (probably the best AFAIK)

First you use the following function to clear all the bits except the highest one:

uint32_t keepHighestBit( uint32_t n )
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

Credit: The idea come from Henry S. Warren, Jr. in his book Hacker's Delight

Then we use an algorithm based on DeBruijn's Sequence to perform a kind of binary search:

uint8_t highestBitIndex8( uint32_t b )
{
    static const uint32_t deBruijnMagic = 0x06EB14F9; // equivalent to 0b111(0xff ^ 3)
    static const uint8_t deBruijnTable[64] = {
         0,  0,  0,  1,  0, 16,  2,  0, 29,  0, 17,  0,  0,  3,  0, 22,
        30,  0,  0, 20, 18,  0, 11,  0, 13,  0,  0,  4,  0,  7,  0, 23,
        31,  0, 15,  0, 28,  0,  0, 21,  0, 19,  0, 10, 12,  0,  6,  0,
         0, 14, 27,  0,  0,  9,  0,  5,  0, 26,  8,  0, 25,  0, 24,  0,
     };
    return deBruijnTable[(keepHighestBit(b) * deBruijnMagic) >> 26];
}

Another version:

void propagateBits(uint32_t *n) {
    *n |= *n >> 1;
    *n |= *n >> 2;
    *n |= *n >> 4;
    *n |= *n >> 8;
    *n |= *n >> 16;
}

uint8_t highestSetBitIndex8(uint32_t b)
{
  static const uint32_t Magic = (uint32_t) 0x07C4ACDD;

  static const int BitTable[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31,
  };
  propagateBits(&b);

  return BitTable[(b * Magic) >> 27];
}

Benchmark with 100 million calls

compiling with g++ -std=c++17 highestSetBit.cpp -O3 && ./a.out

highestBitIndex1  136.8 ms (loop)  
highestBitIndex2  183.8 ms (log(n) / log(2)) 
highestBitIndex3   10.6 ms (de Bruijn lookup Table with power of two, 64 entries)
highestBitIndex4   4.5 ms (inline assembly bsr)
highestBitIndex5   6.7 ms (intrinsic bsr)
highestBitIndex6   4.7 ms (gcc lzcnt)
highestBitIndex7   7.1 ms (inline assembly lzcnt)
highestBitIndex8  10.2 ms (de Bruijn lookup Table, 32 entries)

I would personally go for highestBitIndex8 if portability is your focus, else gcc built-in is nice.

5

With recursion:

int firstset(int bits) {        
     return (bits & 0x80000000) ? 31 : firstset((bits << 1) | 1) - 1;
}
  • Assumes [31,..,0] indexing
  • Returns -1 if no bits set
  • | 1 prevents stack overflow by capping the number of shifts until a 1 is reached (32)
  • Not tail recursive :)
2
  • I do not understand the |1)-1 part. why are you doing that ? Jan 31, 2012 at 12:06
  • 1
    @KshitijBanerjee this sets index of 0 to one after every shift. Otherwise you'll shift forever if the number is zero.
    – calebds
    Jan 31, 2012 at 15:35
3

Floor of logarithm-base-two should do the trick (though you have to special-case 0).

Floor of log base 2 of 0001 is 0 (bit with index 0 is set).
 "           "      of 0010 is 1 (bit with index 1 is set).
 "           "      of 0011 is 1 (bit with index 1 is set).
 "           "      of 0100 is 2 (bit with index 2 is set).
and so on.

On an unrelated note, this is actually a pretty terrible interview question (I say this as someone who does technical interviews for potential candidates), because it really doesn't correspond to anything you do in practical programming.

Your boss isn't going to come up to you one day and say "hey, so we have a rush job for this latest feature, and it needs to be implemented without loops!"

7
  • 2
    I am pretty sure calculating log is more expensive than 32 shifts!
    – ElKamina
    Jan 28, 2012 at 0:28
  • and does'nt log use looping internally? Jan 28, 2012 at 0:30
  • 2
    @ElKamina - The question didn't ask for it to be fast. Kshitij - most code uses looping internally.
    – Amber
    Jan 28, 2012 at 0:32
  • 2
    Also, calculating a logarithm is almost certainly faster than calling a recursive function up to 32 times, due to function call overhead.
    – Amber
    Jan 28, 2012 at 0:40
  • @Jarred which is just another way of saying "use a loop"
    – Amber
    Jan 28, 2012 at 0:56
2

You could do it like this (not optimised):

int index = 0;
uint32_t temp = number;

if ((temp >> 16) != 0) {
    temp >>= 16;
    index += 16;
}

if ((temp >> 8) != 0) {
    temp >>= 8
    index += 8;
}

...
1
  • Compiler will probably store the result of the right shift, but just in case, I would do if ((temp2 = temp >> 16) != 0) { temp = temp2; ... Apr 4, 2012 at 12:30
1

sorry for bumping an old thread, but how about this

inline int ilog2(unsigned long long i) {
  union { float f; int i; } = { i }; 
  return (u.i>>23)-27;
}
...
int highest=ilog2(x); highest+=(x>>highest)-1;
// and in case you need it
int lowest = ilog2((x^x-1)+1)-1;
1

this can be done as a binary search, reducing complexity of O(N) (for an N-bit word) to O(log(N)). A possible implementation is:

int highest_bit_index(uint32_t value)
{ 
  if(value == 0) return 0;
  int depth = 0;
  int exponent = 16;

  while(exponent > 0)
  {
    int shifted = value >> (exponent);
    if(shifted > 0)
    {
      depth += exponent;
      if(shifted == 1) return depth + 1;
      value >>= exponent;
    }
    exponent /= 2;
  }

  return depth + 1;
}

the input is a 32 bit unsigned integer. it has a loop that can be converted into 5 levels of if-statements , therefore resulting in 32 or so if-statements. you could also use recursion to get rid of the loop, or the absolutely evil "goto" ;)

1
  • This returns 1.5 for 1.
    – Lance
    Jan 9, 2021 at 22:40
0

Let n - Decimal number for which bit location to be identified start - Indicates decimal value of ( 1 << 32 ) - 2147483648 bitLocation - Indicates bit location which is set to 1

public int highestBitSet(int n, long start, int bitLocation)
{
    if (start == 0)
    {
        return 0;
    }
    if ((start & n) > 0)
    {
        return bitLocation;
    }
    else
    {
        return highestBitSet(n, (start >> 1), --bitLocation);
    }
}

    long i = 1;
    long startIndex = (i << 31);
    int bitLocation = 32;
    int value = highestBitSet(64, startIndex, bitLocation);
    System.out.println(value);
0
int high_bit_set(int n, int pos)
{
if(pos<0) 
return -1;
else
return (0x80000000 & n)?pos:high_bit_set((n<<1),--pos);
}

main()
{
int n=0x23;
int high_pos = high_bit_set(n,31);
printf("highest index = %d",high_pos);
}

From your main call function high_bit_set(int n , int pos) with the input value n, and default 31 as the highest position. And the function is like above.

0

Paislee's solution is actually pretty easy to make tail-recursive, though, it's a much slower solution than the suggested floor(log2(n));

int firstset_tr(int bits, int final_dec) {

     // pass in 0 for final_dec on first call, or use a helper function

     if (bits & 0x80000000) {
      return 31-final_dec;
     } else {
      return firstset_tr( ((bits << 1) | 1), final_dec+1 );
     }
}

This function also works for other bit sizes, just change the check, e.g.

if (bits & 0x80) {   // for 8-bit
  return 7-final_dec;
}
0

Note that what you are trying to do is calculate the integer log2 of an integer,

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Observe that you can attempt to search more than 1 bit at a time.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

This approach uses a binary search

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Another binary search method, perhaps more readable,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

And because you will want to test these,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}
-3

well from what I know the function Log is Implemented very efficiently in most programming languages, and even if it does contain loops , it is probably very few of them , internally So I would say that in most cases using the log would be faster , and more direct. you do have to check for 0 though and avoid taking the log of 0, as that would cause the program to crash.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.