Turn off the rightmost set bit

In this blog post, I will teach you how to write C/C++ program to turn off the rightmost set bit. After reading this post you able to write an efficient program to turn off the rightmost set bit.

Example,

Input : n = 9

Here's a simple ASCII representation of 9 (an 8-bit integer):

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |  (Example bit values)
+---+---+---+---+---+---+---+---+
                              ^
                              |
                       Clear this Bit (It is right most bit)



Output: 8

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |  (Example bit values)
+---+---+---+---+---+---+---+---+

 

Input : n = 12

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)
+---+---+---+---+---+---+---+---+
                      ^
                      |
               Clear this Bit (It is right most bit)



Output: 8

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |  (Example bit values)
+---+---+---+---+---+---+---+---+

 

Let’s see the problem statements for this question.

Problem Statement: Given an integer n, turn off (unset) the rightmost set bit.

 

Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.

 

1-Using the bitwise AND operator:

You can unset the rightmost set bit in a number by performing a bitwise AND operation between the given number (n) and the number obtained by subtracting one from it (n- 1).

For Example,

Suppose n is 12,

n =12

"n" in binary: 00001100

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


So performing n&(n-1) would give us the required result.

00001100 & 00001011 = 00001000 //8

 

C program to turn off the rightmost set bit:

 

#include <stdio.h>

/*
C program to turn off the rightmost set bit
of a given integer and returns the result
*/
int turnOffRightMostSetBit(unsigned int n)
{
    return n & (n - 1);
}


int main()
{
    unsigned int n = 12;

    printf("Value of n after the unset \
the right most set bit.\n");

    const unsigned int newN = turnOffRightMostSetBit(n);

    printf("n =  %d",newN);

    return 0;
}

Output:

Value of n after the unset the right most set bit.
n = 8

Time Complexity: O(1)
Auxiliary Space: O(1)

 

C++ program to turn off the rightmost set bit:

/*
C++ program to turn off the rightmost set bit
of a given integer and returns the result
*/
#include <iostream>

int turnOffRightMostSetBit(unsigned int n)
{
    return (n & (n - 1));
}

int main()
{
    unsigned int n = 12;
    std::cout <<"Value of n after the unset\
the right most set bit\n";

    const unsigned int newN = turnOffRightMostSetBit(n);

    std::cout <<"n = " << newN <<std::endl;

    return 0;
}

Output:

Value of n after the unset the right most set bit.
n = 8

Time Complexity: O(1)
Auxiliary Space: O(1)

 

 

2-Using the bitwise & and ~ operator:

As you know we use - for two’s complement and ~ for one’s complement. Many people like to rewrite this as,

-n = ~n + 1

So, you can isolate the rightmost set bit in “n” by performing (n & -n).  Now taking the ~ (complement of the value) (n& -n) and performing a & (bitwise AND) with “n” turns off the rightmost set bit.

For Example,

Suppose number n:  11
ASCII representation of n in 8-bit integer: 0 0 0 0 1 0 1 1

Step-1: Isolate right-most set bit by doing (n & -n):

  0 0 0 0 1 0 1 1 (n)
& 1 1 1 1 0 1 0 1 (-n)
------------------
  0 0 0 0 0 0 0 1

 

Step-2: Complement of the right-most set bit ~(n& -n):

  0 0 0 0 0 0 0 1 (n& -n)
~ ---------------
  1 1 1 1 1 1 1 0

 

Step-3: Now ANDing with original number (n & ~(n& -n)):

  0 0 0 0 1 0 1 1 (n)
& 1 1 1 1 1 1 1 0 (~(n& -n))
-----------------
  0 0 0 0 1 0 1 0

 

C program to unset the right-most set bit:

#include <stdio.h>

/*
C program to turn off the rightmost set bit
of a given integer and returns the result
*/
int turnOffRightMostSetBit(unsigned int n)
{
    return (n & ~(n & -n));
}

// Driver Code
int main()
{
    unsigned int n = 11;

    printf("Value of n after the unset\
the right-most set bit\n");

    const unsigned int newN = turnOffRightMostSetBit(n);

    printf("n =  %d",newN);

    return 0;
}

Output:

Value of n after the unset the right-most set bit
n = 10

 

C++ program to unset the right-most set bit:

 

/*
C++ program to turn off the right-most set bit
of a given integer and returns the result
*/
#include <iostream>

int turnOffRightMostSetBit(unsigned int n)
{
    return (n & ~(n & -n));
}

int main()
{
    unsigned int n = 11;
    std::cout <<"Value of n after the unset\
the right most set bit\n";

    const unsigned int newN = turnOffRightMostSetBit(n);

    std::cout <<"n = " << newN <<std::endl;

    return 0;
}

Output:

Value of n after the unset the right most set bit
n = 10

 

Recommended Post