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
- Count Set bits in an Integer.
- Count Set bits in an Integer using the lookup table.
- Rotate bits of a number.
- How to set, clear or toggle a single bit in C/C++?
- Macros for Bit Manipulation in C/C++.
- 5 Ways to Check if Two Integers have Opposite Signs.
- C Program to Find whether a given integer is a power of three or not.
- Operator Precedence And Associativity In C.
- Operators in C language