Find the rightmost set bit in a number (+ toggle it)

Finding the rightmost set bit in a number is a common problem in computer science and is used in many applications, from competitive programming to low-level programming and data compression. In this article, we will explore various techniques to find the rightmost set bit in a number, including bitwise operations and mathematical approaches.

Table of Contents

1. ̥What is a Set bit
2. Understanding bit wise AND (&)
3. Methods
   3.1 Using right shift (>>)
   3.2 Using left shift (<<)
   3.3 Using 2's complement
4. Applications
   4.1 To check Parity of a number
   4.2 To check if a number is a power of 2.
   4.3 Toggling the rightmost setbit

1)What is a Set Bit?

In computer science, a bit is the smallest unit of data that can be stored or manipulated by a computer. A bit can have two values, 0 or 1, and is often used to represent the on/off state of a particular feature or flag. A "set bit" is a bit that is set to 1, meaning that it is "on" or "active."

2) Bitwise AND

The bitwise AND operator is a binary operator that performs the AND operation on each pair of bits in two binary numbers. If both bits are 1, the result is 1. Otherwise, the result is 0.

Methods

Now that we have a basic understanding of what a setbit is and how bitwise AND works, now let us see how to use them to get the rightmost set bit of a number. In this article we'll learn different techniques to find the rightmost setbit of 20

Input : n = 20
Output: The position of rightmost setbit = 3
As binary representation of 20 is 10100, the first setbit (1) is in the third place from the right.

1.Using right shift (>>)

The right shift is the similar to the divide by two operators. The right shift takes two operands, the first operand is the number to be shifted, and the second operand is the number of positions to shift the bits. So we keep shifting the bits to the right until (and also increase the value of cnt, which maintains the position of the first set bit) we get the first setbit.

We use a helper funciton isSet, the funciton takes two argumets the number to be tested and the position of the bit that is being tested.The &1 is used to extract the right most bit, if it's 1 the it returns true.

Time Complexity is O(logn), as we are traversing through all bits of N, and at most there are logn bits.

Code

#include <iostream>
using namespace std;

bool isSet(int n, int pos){
 return (n>>pos)&1;
}

int main(){
 int n = 20; 	//10100
 if(n == 0){
 	cout<<"There is no set bit in n";
 	return 0;
 }

 int cnt = 1;
 for(int i=0; i<8; ++i){
 	if(isSet(n,i)){
 		break;
 	}
 	else{
 		cnt += 1;
 	}
 }
 cout<<"The position of rightmost (first) set bit = "<<cnt;
}

Output
The position of rightmost set bit = 3

Explanation:
We'll start checking for setbit from the righmost position
Binary repersentation of 20 is 0010100
pos 1 has bit 0
pos 2 has bit 0
pos 3 has bit 1
The position of rightmost (first) set bit = 3

2)Using left shift (<<)

First val is initialized to 1, the we keep shifting the binary representaiton of val one bit to the left at each iteratoin and increment cnt by 1 until the bit-wise AND operation between val and n results in a non-zero value,i.e., the rightmost bit of n is set.
The Time complexity is O(logn), because the while loop iterates at most logn times, as the val is shifted one bit to the left at each iteration, and the maximum value of val is n.

Code

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n = 20; 	//10100
	if(n == 0){
		cout<<"There is not setbit in n";
		return 0;
	}
	int val = 1;
	int cnt = 1;
	while((val & n) == 0){
		val = val << 1;
		cnt += 1;
	}
	cout<<"The position of rightmost set bit = "<<cnt;
}

Output
The position of rightmost set bit = 3

Explanation:

Now, in the loop the val keeps shifting the rightmost setbit to the left by 1 pos until it meets the first setbit in n.
The changes shown below happen during the execution of the while loop.

20 is 10100, val is 1
20 is 10100, val is 10
20 is 10100, val is 100

Found the first setbit which is at third position.
The position of rightmost set bit = 3

3)Using 2's complement

This method works by taking two's complement of the input number and performing a bitwise AND operation with the original number. The result will have only the rightmost set bit of the input number set to 1 and all other bits set to 0. This is because the two's complement of a number involves flipping all the bits and adding 1, which effectively creates a mask that isolates the rightmost set bit.The log2 of the resulting number will give the position of the rightmost setbit.

The Time Complexity is O(1), as the time complexity of all operators (&,-) is O(1), and the inbuilt log2() is also O(1).

Code

#include <iostream>
#include <math.h>
using namespace std;

int rightmostSetBit(int n){
return log2((n) & (-n)) + 1;	//adding 1 to convert 0 based idx to 1 based idx
}

int main(){
	int n = 20; 	//10100
	int pos = rightmostSetBit(n);
	cout<<"The position of rightmost set bit = "<<pos;
}

Output

The position of rightmost set bit = 3

Applications:

1.To check Parity of a number

To check the parity of a number, we can use the rightmost setbit property. We can count the number of setbits in the binary representation of the number, if it's odd, parity is odd, otherwise it is even. In the is_odd_parity function, we initialize cnt to 0 and then we loop through the binary representation of the number. In each iteration we use bitwise AND operator to clear the rightmost setbit of the number and we increment the cnt. The loop continues until all setbits are cleared.

Code

#include <iostream>
using namespace std;

bool is_odd_parity(int n){
    int cnt = 0;
    while(n){
        cnt++;
        n &= (n - 1);
    }
    return (cnt % 2 != 0);
}

int main() {
    int n = 20;
    if (is_odd_parity(n)){
        cout<<n<<" has Odd parity";
    } 
    else{
        cout<<n<<" hasEven parity";
    }
    return 0;
}

Output
20 has Even parity

2.Check if a number is a power of 2

• A power of 2 has only on bit set in the binary representation, which is the leftmost bit.
• If we subtract 1 from power of 2, all the bits to the right most the leftmost bit becomes 1.
• Now if we do AND of this with power of 2, the result is 0.

Example, let's consider 8, which is a power of 2. Binary representation of 8 is 1000.Now if we subtract 1 (8-1 = 7), it becomes 0111. Now,

1000
0111 (&)
--------
0000

• The result is 0, which means 8 is a power of 2.

Code

#include <iostream>
using namespace std;

bool isPowerOfTwo(int n) {
    if (n <= 0) {
        return false; // 0 and negative numbers are not powers of 2
    }
    return (n & (n-1)) == 0;
}

int main() {
    int n = 8;
    if(isPowerOfTwo(n)){
    	cout<<n<<" is a power of 2";
    }
    else{
    	cout<<n<<" is not a power of 2";
    }
}

Output

8 is a power of 2

3.Toggling the rightmost setbit

To toggle the rightmost set bit of a number n, we do (n AND (n-1)). Let's see how this works,

• (n - 1) flips all the bits to the right of the rightmost set bit in nu, and leaves the rest of the bits unchanged.

• n AND (n - 1) clears the rightmost set bit in n (since the rightmost set bit in n is flipped in (n - 1).

  EXAMPLE:
  For example, let's say n is 10, which is 1010 in binary. Then,
      (n - 1) is 9, which is 1001 in binary.
      n AND (n - 1) is 8, which is 1000 in binary. 
      This is the result of toggling the rightmost set bit in n.
  

  Code

  #include<iostream>
  using namespaces std;
  
  int toggle_rsetbit(int n){
      return n & (n-1);
  }
  
  int main(){
      int n = 10; //1010
      int result = toggle_rsetbit(n);
      cout<<result;
  }    
  

With this article at OpenGenus, you must have the complete idea of how to find the rightmost set bit in any given interger and also it's various applications.