CODEWITHSUNDEEP
cbinarybit-manipulation
Johannes
Johannes

Reputation: 3099

Get second most significant bit of a number

You are a C programmer given an integer i > 1. Can you write a function msb2 that returns the second most significant bit of it, in other words: given a number, what's the bit to the right of the leftmost 1 bit? I.e in 1011111 it is 0, in 1100000 it is 1.

Not allowed:

Allowed are:

Is there a constant-time (constant in the number of bits, assuming that all C integer operators take constant time, and assuming that the number of bits is not constant) function for msb2?

One idea I head: Given i, we know i & (i >> 1) >= (1<<((int)log2(i)-1)) <=> msb2(i)=1, however, log2(i) can not be computed easily. Maybe this can still be used somehow?

Upvotes: 1

Views: 3616

Answers (5)

Falk H&#252;ffner
Falk H&#252;ffner

Reputation: 5040

You can simply use

x > (x ^ (x >> 1))

The value (x ^ (x >> 1)) will start with 11 if x starts with 10, and with 10 if x starts with 11. Thus, the comparison gives exactly what is needed.

Upvotes: 7

Jens
Jens

Reputation: 72619

If you can get at the leftmost 1 bit (see msb64()), the rest is easy:

#include <stdio.h>
#include <inttypes.h>

uint64_t msb64(uint64_t x);

int main(int argc, char **argv)
{
    uint64_t x, msb;

    if (argv[1] && sscanf (argv[1], "%lu", &x) == 1) {
        msb = msb64(x);
        printf ("msb2(%lu) = %d\n", x, x & (msb >> 1) ? 1 : 0);
    }
    return 0;
}

uint64_t msb64(uint64_t x)
{
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    return x & ~(x >> 1);
}

$ ./a.out 11
msb2(11) = 0
$ ./a.out 15
msb2(15) = 1

Upvotes: 1

Michael Dorgan
Michael Dorgan

Reputation: 12515

clz makes this trivial if it exists. If not, you can compute it constant time as follows. From this thread:

http://community.arm.com/thread/6400

static __INLINE uint32_t __CLZ(uint32_t x) {  
    extern uint8_t const log2Lkup[256];  

    if (x >= 0x00010000U) {  
        if (x >= 0x01000000U) {  
            return 8U - log2Lkup[x >> 24];  
        }  
        else {  
            return 16U - log2Lkup[x >> 16];  
        }  
    }  
    else {  
        if (x >= 0x00000100U) {  
            return 24U - log2Lkup[x >> 8];  
        }  
        else {  
            return 32U - log2Lkup[x];  
        }  
    }  
}

The function would need the log2 (binary logarithm) lookup table defined in a .c file:

uint8_t const log2Lkup[256] = {  
  0U, 1U, 2U, 2U, 3U, 3U, 3U, 3U, 4U, 4U, 4U, 4U, 4U, 4U, 4U, 4U,  
  5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U,  
  6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U,  
  6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U  
};

I left the code intact from the website as an example as modifying the table could make this even easier.

To solve your case, take (32 - clz(x)) - 1 and handle the case where x is 1 or 0 specially as it is undefined. Note: for 64-bit values, just add a few more lookups...

int wantedValue(int x)
{
    if(x <= 1) return -1;

    return (int)(32 - __CLZ(x)) - 1;
}

Upvotes: 0

wildplasser
wildplasser

Reputation: 44230

Naive log(nbits) thing: (without loops!)

#include <stdio.h>

int main(int argc, char **argv)
{
unsigned long org , val;

sscanf(argv[1] , "%lx", &org);

val = org ;

if (val >= (2<<16)) val >>= 16;
if (val >= (2<<8)) val >>= 8;
if (val >= (2<<4)) val >>= 4;
if (val >= (2<<2)) val >>= 2;
if (val >= (2<<1)) val >>= 1;
if (val <= 2) val <<= 1; // This is needed for org = 1 ;-)

printf("%lx -> %lx %c\n"
    , org, val, val&1 ? '+' : '-');

return 0;
}

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49803

I believe this technically meets the criteria: Write 63 if statements (assuming your integers are 64 bits in size), one for each possible solution. Yes, that basically mimics what a loop would do, but it is still constant time (which the corresponding loop would be, actually, but a tiny bit harder to argue).

Upvotes: 0

Related Questions