Find most significant set bit in a long

Question

I'm in the unique situation where searching for "most significant bit" yields too many results and I can't find an answer that fits my needs!

The question itself is pretty simple: "How do I find the most significant set bit in an unsigned long?" When I do my calculations the rightmost bit position is position '0'.

I know that it involves masking the lowest bit, checking and then shifting left to once while incrementing my count, and then repeating with the 2nd lowest, etc.

I've done this before but for whatever reason I can't do it now.

Edit: By "most significant" I mean leftmost set bit, sorry for any confusion!*

Below is my functioning solution and a few test cases:

#include <stdio.h>

int findExponent( unsigned long L ){

    int exponent = -1;

    unsigned long shift = L;

    while( 0 != shift )
        exponent++, shift >>=1;

    if ( exponent >= 0 )
        printf("The most significant bit of L is at position %d\n", exponent);
    else{
        exponent = 0;
        printf("L is zero\n");
    }
    return exponent;
}


int main(int argc, char** argv){

    long check = 8L;

    findExponent( check );//2
    findExponent( 21421L );//14
    findExponent( 0L );//(is zero)
    findExponent( 1L );//0
}

"most significant bit" and "rightmost bit" might be different things — LihO, Sep 22 '13 at 03:36
Did I make a typo somewhere? I'm sorry if I did. I mean to find the leftmost set bit. — Joshua, Sep 22 '13 at 03:37
@LihO: True, but that's explanatory, i.e. bit position values increase going right to left starting from 0. — Ignacio Vazquez-Abrams, Sep 22 '13 at 03:38
possible duplicate of [What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?](http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i) — parvus, Sep 08 '15 at 07:42

score 4 · Accepted Answer · answered Sep 22 '13 at 04:00

"How do I find the most significant bit in an unsigned long?"

You can do shifts to the right until the last 1 is droped. In this moment, the value becomes 0.

#include <stdio.h>
int main(void) {
          unsigned long x = 3333;
          unsigned long y = x;
          int p = -1;
          while (0 != y)
              p++, y >>= 1;
          if (p >= 0)
              printf("The most significative bit of x is at position %d\n", p);
          else
              printf("x is zero\n");
}

I actually thought of something very similar while laying in bed this morning! Guess I just needed some sleep:) I like the p++, y >>=1, more compact than my idea. — Joshua, Sep 22 '13 at 15:45

Ignacio Vazquez-Abrams · Answer 2 · 2013-09-22T03:51:40.987

0

Perform left shifts until the signed value is less than 0 (if ((signed long)x < 0)), then subtract the number of shifts performed from the MSb position value (or just decrement instead).

edited Sep 22 '13 at 03:51

answered Sep 22 '13 at 03:36

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

"How do I find the most significant bit in an unsigned long?" – pablo1977 Sep 22 '13 at 03:49
Missed that bit. Fortunately you can cast it in the comparison and the compiler will DTRT. – Ignacio Vazquez-Abrams Sep 22 '13 at 03:50

score -1 · Answer 3 · answered Jul 08 '17 at 02:46

-1

unsigned long x = val & ((~0ULL >> 1) ^ (~0ULL));

of course if the value is signed all negatives have one in the most significative bit otherwise zero :)

shift right and XOR with one's... in an 8 bit example.

0011 1100 -> val
1111 1111 -> (~0)
0111 1111 -> (~0 >> 1)
1000 0000 -> ((~0 >> 1) ^ (~0))
0000 0000 -> val & ((~0 >> 1) ^ (~0))  !most significant bit from val is zero

answered Jul 08 '17 at 02:46

mvcorrea

101
1
8

1

As OP clarified, he actually wanted the position of the leftmost set bit, not the value of the msb. – harold Jul 08 '17 at 03:03

Find most significant set bit in a long

3 Answers3

Linked

Related