Given a non-negative number n. The problem is to set the rightmost unset bit in the binary representation of n
Examples:
Input : 21
Output : 23
(21)10 = (10101)2
Rightmost unset bit is at position 2(from right) as
highlighted in the binary representation of 21.
(23)10 = (10111)2
The bit at position 2 has been set.
Input : 2
Output : 3
One method is discussed in this article
This post discusses another method.
Let the input number be n. n+1 would have all the bits flipped after the rightmost unset bit (including the unset bit). So, doing n|(n+1) would give us the required result.
C++
#include <stdio.h>
int fun(unsigned int n)
{
return n | (n + 1);
}
int main()
{
int n = 5;
printf ( "The number after setting the" );
printf ( " rightmost unset bit %d" , fun(n));
return 0;
}
|
Java
class GFG {
static int fun( int n)
{
return n | (n + 1 );
}
public static void main(String[] args)
{
int n = 5 ;
System.out.printf( "The number "
+ "after setting the" );
System.out.printf( " rightmost "
+ " unset bit %d" , fun(n));
}
}
|
Python3
def fun(n):
return n | (n + 1 )
n = 5
print ( "The number after setting the" , end = "")
print ( " rightmost unset bit " , fun(n))
|
C#
using System;
class GFG {
static int fun( int n)
{
return n | (n + 1);
}
public static void Main()
{
int n = 5;
Console.Write( "The number "
+ "after setting the" );
Console.Write( " rightmost "
+ "unset bit " + fun(n));
}
}
|
Javascript
<script>
function fun(n)
{
return n | (n + 1);
}
let n = 5;
document.write( "The number after setting the" );
document.write( " rightmost unset bit " , fun(n));
</script>
|
PHP
<?php
function fun( $n )
{
return $n | ( $n + 1);
}
$n = 5;
echo "The number after setting the" ;
echo " rightmost unset bit " , fun( $n );
?>
|
Output
The number after setting the rightmost unset bit 7
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach#2: Using bin
This approach sets the rightmost unset bit of a given integer by converting it to binary, finding the first ‘0’, setting it to ‘1’, and then converting the binary string back to integer.
Algorithm
1. Convert the number n to binary and reverse the string.
2. Find the index of the first ‘0’ in the binary string.
3. If there are no unset bits, return n.
4. Set the rightmost unset bit by changing the character at the index found in step 2 to ‘1’.
5. Convert the binary string back to an integer and return.
C++
#include <iostream>
#include <bitset>
using namespace std;
unsigned int setRightmostUnsetBit(unsigned int n) {
if (n == 0) {
return 1;
}
unsigned int mask = 1;
while (n & mask) {
mask <<= 1;
}
n |= mask;
return n;
}
int main() {
unsigned int n = 5;
cout << "The number after setting the rightmost unset bit: " << setRightmostUnsetBit(n) << endl;
return 0;
}
|
Java
public class Main {
static int setRightmostUnsetBit( int n) {
if (n == 0 ) {
return 1 ;
}
int mask = 1 ;
while ((n & mask) != 0 ) {
mask <<= 1 ;
}
n |= mask;
return n;
}
public static void main(String[] args) {
int n = 5 ;
System.out.println( "The number after setting the rightmost unset bit: " + setRightmostUnsetBit(n));
}
}
|
Python3
def setRightmostUnsetBit(n):
binary = bin (n)[ 2 :][:: - 1 ]
index = binary.find( '0' )
if index = = - 1 :
return n
binary = binary[:index] + '1' + binary[index + 1 :]
return int (binary[:: - 1 ], 2 )
n = 5
print ( "The number after setting the" , end = "")
print ( " rightmost unset bit " , setRightmostUnsetBit(n))
|
C#
using System;
class GFG
{
static uint SetRightmostUnsetBit( uint n)
{
if (n == 0)
{
return 1;
}
uint mask = 1;
while ((n & mask) != 0)
{
mask <<= 1;
}
n |= mask;
return n;
}
static void Main()
{
uint n = 5;
Console.WriteLine( "The number after setting the rightmost unset bit " + SetRightmostUnsetBit(n));
}
}
|
Javascript
function GFG(n) {
let binary = n.toString(2).split( '' ).reverse().join( '' );
let index = binary.indexOf( '0' );
if (index === -1) {
return n;
}
binary = binary.slice(0, index) + '1' + binary.slice(index + 1);
return parseInt(binary.split( '' ).reverse().join( '' ), 2);
}
const n = 5;
console.log( "The number after setting the rightmost unset bit:" , GFG(n));
|
Output
The number after setting the rightmost unset bit 7
Time complexity: O(log n)
Space complexity: O(log n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!