Fastest way to find binary base [duplicate]

Question

I am trying to find binary base of a number, like the floor function which rounds of number to greatest integer below it, i want to round off the number to the 1st binary base below it.

For example:

for 1000 it should be 512
for 10 it should be 8
for 208 it should be 128

This is what I've tried. I feel log functions will consume more resources so is there any faster approach for this?

#include<stdio.h>
int main()  {
    unsigned long long int num;
    unsigned long long int mask;
    scanf("%llu", &num);
    mask = 0x80000000;
    while(mask >>= 1)   {
        if (mask & num)
            break;
    }
    printf("%llu\n", mask);
    return 0;
}

Thanks:)

Answer 1

int topBit(int n) {
    while (true){
        m = n & (n-1);
        if (m == 0) return n;
        n = m;
    } 
}

n & (n-1) clears the bottom most set bit. Just do this until you hit zero, and then you know the previous value had only one bit set (the highest that was set in the input).

Answer 2

Represent the number in binary, then look for the most significant bit (the highest nonzero bit). Naively you can do this by right shifting one bit at a time until it is zero - that was "one too many". That is basically the approach you tried. A bit faster would be a binary search. For 32 bit integer, shift right by 16; if still > 0, right shift by 8, etc. I'm sure you can figure it out from here.

Code example:

typedef unsigned long long int ulli;
ulli floor2(ulli num){
  int msb = 8*sizeof(num)/2;
  ulli temp = ((ulli)1)<<msb;
  while(msb>1){
    msb/=2; // using divide for clarity
    if(temp>num) temp>>=msb; else temp<<=msb;
  }
  if (temp>num) temp/=2;
  return temp;
}

I ran some benchmarks of this algorithm against the topBit as well as the builtIn method. A loop with 10M iterations, generating a "long" random number, takes 362 ms on my system (with no compiler optimization). If the loop includes one of the methods of calculation, times increase as follows:

=============  total    net
builtin:         407     45
binary search:   579    215
topBit:         2295   1933

The built in method is definitely the fastest by a significant margin - not really surprising! With 64 bit numbers, topBit will on average need 32 loops (half the bits are set, so get skipped) and binary only 5 loops, so you would expect about 6x speed difference; that is roughly what you see. When I define ulli as unsigned short (16 bit), the time difference is about 2x.