Fastest way to find binary base

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.

Answer 3

You can do this using GCC builtins, if you're compiling with GCC. The builtin __builtin_clzll counts the number of leading zeros in an unsigned long long. You can use it to calculate the position of the most significant bit, and then left shift 1 that many times to get your answer:

#include <limits.h>

Then use:

unsigned long long result = 
  num ? 1LLU << (sizeof(unsigned long long)*CHAR_BIT - __builtin_clzll(num) - 1) : 0;

printf("%llu\n", result);

Answer 4

This classic document has many ways to find the floor(log base 2) of an integer. After you've found the log, the number you want is of course 1 << log.

The most fascinating suggestion is this

// Find the integer log base 2 of an integer with an 64-bit IEEE float 
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

The code above loads a 64-bit (IEEE-754 floating-point) double with a 32-bit integer (with no paddding bits) by storing the integer in the mantissa while the exponent is set to 252. From this newly minted double, 252 (expressed as a double) is subtracted, which sets the resulting exponent to the log base 2 of the input value, v. All that is left is shifting the exponent bits into position (20 bits right) and subtracting the bias, 0x3FF (which is 1023 decimal). This technique only takes 5 operations, but many CPUs are slow at manipulating doubles, and the endianess of the architecture must be accommodated.

So the final result you want will be 1 << r. Note that manipulation of doubles is much faster now than when this article was written. The best thing about this code is that it contains no branches, so will pipeline nicely. You should definitely give it a try. I don't have time to try a benchmark just now, but it would be interesting.

I can't vouch that this code meets the C Standard.

Answer 5

I assume that if a number is already a power of 2 or zero, it should be returned without change. Positive numbers only.

int floor2(int n)
{
    if ((n & (n-1)) == 0)
        return n;
    while (((n+1) & n) != 0)
    {
        n = n | (n+1);
    }
    return (n + 1) >> 1;
}

The fancy bit twiddling here takes advantage of the fact that subtracting 1 from a number with a single bit (i.e. a power of 2) sets all the bits below it, while adding 1 to a number will set the bottom-most zero bit.

Answer 6

This is problem is very closely related to finding the most significant bit problem; because after that it's just a bit of bit shifting:

Finding MSB is well described here:

Find most significant bit (left-most) that is set in a bit array

and then you do something like this:

int foo = 1000;
int bar = ((msb(foo) << 1) - 1) >> 1; 
if ( bar > foo ) bar = bar >> 1; 

and you have it.

If you're on intel architecture you can use __builtin_clz (calculate leading zeros) in gcc to get the msb;

Or

Here is a really fun way to do calculate leading zeros without CPU support

http://www.hackersdelight.org/hdcodetxt/nlz.c.txt

Answer 7

Short and sweet ...
(Questioner's sample code had trouble with values >= 0x80000000LLU, fixed here.)
This needs only 1 compare in the loop rather than 2.

unsigned long long int MSMask(unsigned long long int) {
  if (num == 0) {
    return 0;
    }
  else {
    unsigned long long int mask = 0x8000000000000000LLU;
    while (!(mask & num)) mask >>= 1;
    return mask;
  }
}

Answer 8

This is about 2 times faster than your version:

uint64_t g(uint64_t num) {
    uint64_t r = 1;
    num = num >> 1;
    while(num>r)   {
        r <<= 1;
    }
    return r;
}

Answer 9

int test(int num) {
    int res = (num==0?0:1);
    while(num>1) {
        num=num>>1;
        res=res<<1;
    }
    return res;
}

faster than below when num is not large.

Answer 10

The worst case performance of the suggested bit twiddling tricks could / should be improved by gradually oring several bits to be ones:

 int s=1;
 while ((n+1) & n) {
    n|=n >> s;
    s<<=1;
 }
 return (n+1) >> 1;

This fragment exits when all the least significant bits are ones, requiring only some log2(log2(n)) iterations.

Answer 11

I know recursion is generally not as efficient as iteration, but I can't help myself -- I love a good recursion:

unsigned topBit(unsigned n) {
   unsigned m = n & (n-1);
   return m ? topBit(m) : n;
}

ADDENDUM: Actual timings showed this as slightly faster than @LaurenceGonsalves's iterative version when compiled with optimization.