How to get position of right most set bit in C

Question

int a = 12;

for eg: binary of 12 is 1100 so answer should be 3 as 3rd bit from right is set.

I want the position of the last most set bit of a. Can anyone tell me how can I do so.

NOTE : I want position only, here I don't want to set or reset the bit. So it is not duplicate of any question on stackoverflow.

Edric

@rost0031 that's not the same question. ramsingh please show what you have tried so far – Heartrending

I want exact position. I don't want to set or reset it. – Edric

I want it to be done in one step. – Edric

@RyanHaining I've tried on paper, so can you please tell me how to show it here. – Edric

See also Position of least significant bit that is set – Lattonia

Answer 1

Try this

int set_bit = n ^ (n&(n-1));

Explanation:
As noted in this answer, n&(n-1) unsets the last set bit.
So, if we unset the last set bit and xor it with the number; by the nature of the xor operation, the last set bit will become 1 and the rest of the bits will return 0

Shockey

Why does this produce the correct result? A little bit of explanation would be helpful. – Encratia

Try to solve it on paper you'll get the point. I still it is not clear, let me know I'll explain. It's very easy concept. – Shockey

@harold you did not understood it properly. the question is very clear. – Edric

@ramsingh, you asked for the POSITION not the VALUE of the bit. – Falgoust

For a = 8, what should be the answer? – Encratia

@dbush in my compiler range of int is more than 32767. – Edric

This returns an int that is a power of two: it has only that bit set that is the right most set bit in n. I suppose it is down voted because the OP asked for the log2 of that (plus one). Ie, for 1100b it will return 100b (4), instead of log2(4) + 1 = 3. I didn't down vote this, I think it's still useful. – Tesler

this doesn't answer the question. For example for 12 it gives 8 instead of 3 like the OP expected – Minor

...how in the world can this be the accepted answer? – Mannerheim

This does not give right result. This answer should be removed from SO. – Dungaree

Answer 2

This answer Unset the rightmost set bit tells both how to get and unset rightmost set bit for an unsigned integer or signed integer represented as two's complement.

get rightmost set bit,

x & -x
// or
x & (~x + 1)

unset rightmost set bit,

x &= x - 1
// or
x -= x & -x  // rhs is rightmost set bit

why it works

x:                     leading bits  1  all 0
~x:           reversed leading bits  0  all 1
~x + 1 or -x: reversed leading bits  1  all 0
x & -x:                       all 0  1  all 0

eg, let x = 112, and choose 8-bit for simplicity, though the idea is same for all size of integer.

// example for get rightmost set bit
x:             01110000
~x:            10001111
-x or ~x + 1:  10010000
x & -x:        00010000

// example for unset rightmost set bit
x:             01110000
x-1:           01101111
x & (x-1):     01100000

Thankful

This is a good explanation, but is an incorrect answer. This code returns an integer with only the right-most set bit set, but it doesn't do what the question asks and return the bit position of that bit (+1 per the OP). – Kalamazoo

Answer 3

Finding the (0-based) index of the least significant set bit is equivalent to counting how many trailing zeros a given integer has. Depending on your compiler there are builtin functions for this, for example gcc and clang support __builtin_ctz. For MSVC you would need to implement your own version, this answer to a different question shows a solution making use of MSVC intrinsics.

Given that you are looking for the 1-based index, you simply need to add 1 to ctz's result in order to achieve what you want.

int a = 12;
int least_bit = __builtin_ctz(a) + 1; // least_bit = 3

Note that this operation is undefined if a == 0. Furthermore there exist __builtin_ctzl and __builtin_ctzll which you should use if you are working with long and long long instead of int.

C++20 update

As part of P0553 __builtin_ctx was standardized as

template <class T>
constexpr int countr_zero(T x) noexcept;

So in case using C++20 is an option for you, you no longer need to rely on compiler builtins, and can simply depend on the standard library.

In contrast to __builtin_ctx std::countr_zero() is templated and thus can be used with any unsigned integer type. However, it does not support signed types:

int a = 12;
int least_bit = std::countr_zero(a) + 1; // compiler error since `int` is signed

unsigned int a = 12u;
int least_bit = std::countr_zero(a) + 1; // least bit = 3

As a side effect invoking std::countr_zero() with a zero argument is well defined, and will return the number of bits present in the given integer type T, i.e. sizeof(T) * CHAR_BIT.

Mckinley

Hi, seems the best solution (!). Suggestion to complement explanations... There are some confusion, about "right most", "left most", "starting at the most significant bit position", and "... least significant ...". So confusion about CLZ and CTZ, and its __builtin_cXz... Can you explain also the jargon and CLZ/CTZ choice? – Morose

I disagree that right-most and left-most are confusing here. Anyone who has ever counted to ten on paper knows that the right digit is less significant than the left digit. – Kalamazoo

I think this is the best answer. It solves the right problem and it does so in constant time and doesn't require a log function. – Kalamazoo

Answer 4

One can use the property of 2s-complement here.
Fastest way to find 2s-complement of a number is to get the rightmost set bit and flip everything to the left of it.

For example: consider a 4 bit system

/* Number in binary */
4 = 0100
/* 2s complement of 4 */
complement = 1100 
/* which nothing but */
complement == -4
/* Result */
4 & (-4) = 0100

Notice that there is only one set bit and its at rightmost set bit of 4.

Similarly we can generalise this for n.
n&(-n) will contain only one set bit which is actually at the rightmost set bit position of n.

Since there is only one set bit in n&(-n), it is a power of 2.
So finally we can get the bit position by:

log2(n&(-n))+1

Lascar

Should this solution explicitly handle the case when (n & -n) == 0? Because log2(0) produce -inf which is not a valid integer? – Mustard

and that can happen only when n = 0 which you might need to explicitly check. – Lascar

Answer 5

There is a neat trick in Knuth 7.1.3 where you multiply by a "magic" number (found by a brute-force search) that maps the first few bits of the number to a unique value for each position of the rightmost bit, and then you can use a small lookup table. Here is an implementation of that trick for 32-bit values, adapted from the nlopt library (MIT/expat licensed).

/* Return position (0, 1, ...) of rightmost (least-significant) one bit in n.
 *
 * This code uses a 32-bit version of algorithm to find the rightmost
 * one bit in Knuth, _The Art of Computer Programming_, volume 4A
 * (draft fascicle), section 7.1.3, "Bitwise tricks and
 * techniques." 
 *
 * Assumes n has a 1 bit, i.e. n != 0
 *
 */
static unsigned rightone32(uint32_t n)
{
    const uint32_t a = 0x05f66a47;      /* magic number, found by brute force */
    static const unsigned decode[32] = { 0, 1, 2, 26, 23, 3, 15, 27, 24, 21, 19, 4, 12, 16, 28, 6, 31, 25, 22, 14, 20, 18, 11, 5, 30, 13, 17, 10, 29, 9, 8, 7 };
    n = a * (n & (-n));
    return decode[n >> 27];
}

Clemmieclemmons

Answer 6

The leftmost bit of n can be obtained using the formulae: n & ~(n-1)

This works because when you calculate (n-1) .. you are actually making all the zeros till the rightmost bit to 1, and the rightmost bit to 0. Then you take a NOT of it .. which leaves you with the following: x= ~(bits from the original number) + (rightmost 1 bit) + trailing zeros

Now, if you do (n & x), you get what you need, as the only bit that is 1 in both n and x is the rightmost bit.

Phewwwww .. :sweat_smile:

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/ helped me understand this.

Dexterous

I think you mean "The rightmost bit of n can be obtained using the formulae: n & ~(n-1)"? other than that, this answer is perfect to explain why not just how. – Translucent

As with other answers, this is a good explanation, but is an incorrect answer. This code returns an integer with only the right-most set bit set, but it doesn't do what the question asks and return the bit position of that bit (+1 per the OP). – Kalamazoo

Answer 7

1- Subtract 1 form number: (a-1)

2- Take it's negation : ~(a-1)

3- Take 'AND' operation with original number:

int last_set_bit = a & ~(a-1)

The reason behind subtraction is, when you take negation it set its last bit 1, so when take 'AND' it gives last set bit.

Hiltonhilum

Answer 8

Check if a & 1 is 0. If so, shift right by one until it's not zero. The number of times you shift is how many bits from the right is the rightmost bit that is set.

Cloe

It's not a one-liner but it is the simplest method. Easy to implement anywhere too. – Perfervid

Answer 9

You can find the position of rightmost set bit by doing bitwise xor of n and (n&(n-1) )

int pos = n ^ (n&(n-1));

Conk

Are you sure this piece of code gives the position of rightmost set bit? – Quoth

This is wrong. If n=4 or 0b100, the answer should be 2, assuming 0 indexing. 100 & 011 = 000; 100 ^ 000 = 100, which is 4 instead of the expected 2. – Hurdle

Answer 10

I inherited this one, with a note that it came from HAKMEM (try it out here). It works on both signed and unsigned integers, logical or arithmetic right shift. It's also pretty efficient.

#include <stdio.h>

int rightmost1(int n) {
    int pos, temp;
    for (pos = 0, temp = ~n & (n - 1); temp > 0; temp >>= 1, ++pos);
    return pos;
}

int main()
{
    int pos = rightmost1(16);
    printf("%d", pos);
}

Hurdle

Answer 11

You must check all 32 bits starting at index 0 and working your way to the left. If you can bitwise-and your a with a one bit at that position and get a non-zero value back, it means the bit is set.

#include <limits.h>

int last_set_pos(int a) {
  for (int i = 0; i < sizeof a * CHAR_BIT; ++i) {
    if (a & (0x1 << i)) return i;
  }
  return -1; // a == 0
}

On typical systems int will be 32 bits, but doing sizeof a * CHAR_BIT will get you the right number of bits in a even if it's a different size

Heartrending

Answer 12

Accourding to dbush's solution, Try this:

int rightMostSet(int a){
      if (!a) return -1;  //means there isn't any 1-bit
      int i=0;
      while(a&1==0){ 
        i++; 
        a>>1;
      }
      return i;
    }

Bullace

It would be easier to check if the number is zero (i.e. all bits are zero) before entering the loop. – Encratia

Answer 13

return log2(((num-1)^num));

explanation with example number: 12 #1100 in binary

num-1 = 11 #1011

num^ (num-1) = 12^11 = 7 #0111

num^ (num-1)) = 8 #1000

log2(1000) = 3 (answer)....

Incomplete

Answer 14

x & ~(x-1) isolates the lowest bit that is one.

Appurtenant

Answer 15

int main(int argc, char **argv)
{
    int setbit;
    unsigned long d;
    unsigned long n1;
    unsigned long n = 0xFFF7;
    double nlog2 = log(2);

    while(n)
    {
        n1 = (unsigned long)n & (unsigned long)(n -1);
        d = n - n1;
        n = n1;

        setbit = log(d) / nlog2;
        printf("Set bit: %d\n", setbit);
    }

    return 0;
}

And the result is as below.

Set bit: 0
Set bit: 1
Set bit: 2
Set bit: 4
Set bit: 5
Set bit: 6
Set bit: 7
Set bit: 8
Set bit: 9
Set bit: 10
Set bit: 11
Set bit: 12
Set bit: 13
Set bit: 14
Set bit: 15

Dungaree

Answer 16

Let x be your integer input. Bitwise AND by 1. If it's even ie 0, 0&1 returns you 0. If it's odd ie 1, 1&1 returns you 1.

if ( (x & 1) == 0) ) 
{
        std::cout << "The rightmost bit is 0 ie even \n";
}
else
{
        std::cout<< "The rightmost bit is 1 ie odd \n";
}```

Mariomariology

There are fifteen existing answers to this question, including an answer with 30 upvotes. Are you sure your answer hasn't already been provided? If not, why might someone prefer your approach over the existing approaches proposed? Are you taking advantage of new capabilities? Are there scenarios where your approach is better suited? – Ceraceous

Answer 17

Alright, so number systems is just working with logarithms and exponents. So I'll dive down into an approach that really makes sense to me.

I would prefer you read this because I write there about how I interpret logarithms as.

When you perform the x & -x operation, it gives you the value which has the right most bit as 1 (for example, it can be 0001000 or 0000010. Now according to how I interpret logarithms as, this value of the right most set bit, is the final value after I grow at the rate of 2. Now we are interested in finding the number of digits in this answer because whatever that is, if you subtract 1 from it, that is precisely the bit-count of set bit (bit count begins with 0 here and the digit count begins with 1, so yeah). But the number of digits is precisely the time you expanded for + 1 (in accordance with my logic) or just the formula I mentioned in the previous link. But now, as we don't really need the digits, but need the bit count, and we also don't have to worry about values of bits which potentially can be real (if the number is 65) because the number is always some multiple of 2 (except 1). So if you just take the logarithm of the value x & -x, we get the bit count! I did see an answer before that mentioned this, but diving down to why it really works was something I felt like writing down.

P.S: You could also count the number of digits and then subtract 1 from it to get the bit-count.

Rheometer

Answer 18

Suppose n is 12,

n =12
"n" in binary: 00001100


**Step 1:** n-1 > 11
/*
n-1 would have all the bits flipped after 
the rightmost set bit (including the set bit).
*/
"n"−1 in binary: 00001011



**Step 2:** ∼(n−1) (Complement of n−1)

∼(n−1) in binary: 11110100



**Step 3:** (n & ~(n - 1)):

((00001100) & (11110100)) is 00000100
You can see in step 3 on rightmost bit is set and other bits set to 0


**Step 4:** log2(n & ~(n - 1)):

/* calculates the position of the 
  rightmost set bit in a given number n.
*/

If n is 12 it returns 2, See the pictorial representation
for better understanding.
Here's a simple ASCII representation of 12 (an 8-bit integer):
  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |  (Example bit values)
+---+---+---+---+---+---+---+---+
                      ^
                      |
               2 is the position of rightmost set bit.

Reference: https://aticleworld.com/position-of-right-most-set-bit/

Crying