Can you find the rightmost set bit in a binary number?

It is possible to find the rightmost set bit (i.e., 1) in a binary number using bitwise operations in programming.

Firstly, let’s understand the bitwise AND (&) operation. The operation takes two numbers as operands and does AND on every bit of the binary representations of the numbers. If both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 & 1 = 1). Otherwise, the result is 0 (0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0).

To find the rightmost set bit, we can take advantage of this operation and the properties of binary number subtraction. When a binary number (let’s call it n) is subtracted by 1, the rightmost 1 in the binary representation of n flips to 0, and all the bits to the right of this bit also flip.

For example,

Let n = 40, which is 101000 in binary

n-1 = 39, which is 100111 in binary

When you perform bitwise AND operation on n and n - 1, only the part up to the rightmost set bit in n (including this bit) becomes 0.

n&(n-1) = 101000 & 100111 = 100000, which is 32 in decimal

To reveal the rightmost bit, we can subtract the result from the original number:

n-(n&(n-1)) = 101000 - 100000 = 1000 = 8 in decimal

This gives the rightmost set bit in the binary representation of n which is the number 8 in decimal.

So the formula to find the rightmost set bit can be given by:

r = n - (n & (n - 1))

Where ‘n‘ represents the binary number and ‘r‘ is the rightmost set bit. Here, ’&’ refers the bitwise AND operation.

For instance, if you want to find the rightmost set bit of 40(101000 in binary), you would do:

40 - (40 & (40 - 1)) = 8

This formula indicates that the rightmost set bit of the binary representation of 40 is 8 (which is 23̂, corresponding to the fourth bit from right in binary representation).