Remove nth bit of a number
The given problem is about removing the nth bit of a given number. We are provided with a positive integer
num
and an integer n
representing the position of the bit to be removed (1-indexed, from
right to left). The task is to remove the nth bit from the binary representation of the number and return the
resulting number.
Problem Statement
Given a positive integer num
and an integer n
, remove the nth bit from the binary
representation of num
and return the resulting number.
Example
Let's take an example to illustrate the problem. Consider num = 21
and n = 3
. The binary
representation of 21
is 10101
. After removing the 3rd bit (from right to left), we get
1001
, which is 9
in decimal.
Pseudocode
Before diving into the algorithm, let's start with a pseudocode representation of the approach to remove the nth bit:
FUNCTION removeBit(num, n):
IF n < 1 OR num < 0:
RETURN
value = 1 << (n - 1)
IF value > num:
PRINT "Output:", num
RETURN
result = num XOR value
value = value - 1
value = result AND value
result = result - value
value = value << 1
result = result OR value
result = result >> 1
PRINT "Output:", result
Algorithm Explanation
- The function
removeBit(num, n)
takes the numbernum
and the positionn
of the bit to be removed as inputs. - We first check if the value of
n
is less than 1 or ifnum
is negative. If either condition is true, we return from the function since it's not possible to remove a bit in these cases. - We calculate the value of
1
left-shifted by(n - 1)
positions, which will set the nth bit to1
and all other bits to0
. - If the calculated value is greater than
num
, then removing the bit will not affect the given number, so we print the output as the original numbernum
. - If the calculated value is not greater than
num
, we proceed to remove the nth bit. - We use bitwise XOR operation (
^
) to deactivate the nth bit, effectively setting it to0
while keeping other bits unchanged. - We subtract
1
from the calculated value, which will result in all1
s from the nth position (inclusive) to the rightmost bit (inclusive). - We use bitwise AND operation (
&
) with the result to unset all the bits from the nth position to the rightmost bit, effectively removing the nth bit. - We update the
result
by subtracting the calculated value, effectively removing the nth bit. - We shift the value one position to the left using bitwise left shift (
<<
) to prepare it to be added to the result in the next step. - We use bitwise OR operation (
|
) with the result to add the new left portion obtained from the previous step. - Finally, we shift the result one position to the right using bitwise right shift (
>>
) to remove the extra zero bit added in the previous step. - We print the final output, which is the number obtained after removing the nth bit.
Resultant Output Explanation
The code uses the algorithm described above to remove the nth bit from the given numbers and prints the output.
- For
num = 21
andn = 3
, the output is9
. The binary representation of21
is10101
, and after removing the 3rd bit, we get1001
, which is9
in decimal. - For
num = 73
andn = 5
, the output is41
. The binary representation of73
is1001001
, and after removing the 5th bit, we get101001
, which is41
in decimal. - For
num = 80
andn = 7
, the output is16
. The binary representation of80
is1010000
, and after removing the 7th bit, we get10000
, which is16
in decimal. - For
num = 11
andn = 5
, the output is11
. The binary representation of11
is01011
, and after removing the 5th bit, we get1011
, which is11
in decimal. - For
num = 6
andn = 1
, the output is3
. The binary representation of6
is110
, and after removing the 1st bit, we get11
, which is3
in decimal.
Code Solution
Here given code implementation process.
// C Program
// Remove nth bit of a number
#include <stdio.h>
// Remove a Bit at given position of a number
void removeBit(int num, int n)
{
if (n < 1 || num < 0)
{
return;
}
int value = (1 << (n - 1));
// Display result
printf("\n Given Number : %d", num);
printf("\n Remove Bit : %d-th", n);
if (value > num)
{
// When after remove bit is not effect to given number
printf("\n Output : %d\n", num);
return;
}
int result = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
printf("\n Output : %d\n", result);
}
int main(int argc, char const *argv[])
{
// num = 21, n = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
removeBit(21, 3);
// num = 73 n = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
removeBit(73, 5);
// num = 80 n = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
removeBit(80, 7);
// num = 11 n = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
removeBit(11, 5);
// num = 6 n = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
removeBit(6, 1);
return 0;
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
/*
Java program
Remove nth bit of a number
*/
public class BitManipulation
{
// Remove a Bit at given position of a number
public void removeBit(int num, int n)
{
if (n < 1 || num < 0)
{
return;
}
int value = (1 << (n - 1));
// Display result
System.out.print("\n Given Number : " + num);
System.out.print("\n Remove Bit : " + n + "-th");
if (value > num)
{
// When after remove bit is not effect to given number
System.out.print("\n Output : " + num + "\n");
return;
}
int result = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
System.out.print("\n Output : " + result + "\n");
}
public static void main(String[] args)
{
BitManipulation task = new BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Remove nth bit of a number
*/
class BitManipulation
{
public:
// Remove a Bit at given position of a number
void removeBit(int num, int n)
{
if (n < 1 || num < 0)
{
return;
}
int value = (1 << (n - 1));
// Display result
cout << "\n Given Number : " << num;
cout << "\n Remove Bit : " << n << "-th";
if (value > num)
{
// When after remove bit is not effect to given number
cout << "\n Output : " << num << "\n";
return;
}
int result = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result &value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
cout << "\n Output : " << result << "\n";
}
};
int main()
{
BitManipulation task = BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
return 0;
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
// Include namespace system
using System;
/*
C# program
Remove nth bit of a number
*/
public class BitManipulation
{
// Remove a Bit at given position of a number
public void removeBit(int num, int n)
{
if (n < 1 || num < 0)
{
return;
}
int value = (1 << (n - 1));
// Display result
Console.Write("\n Given Number : " + num);
Console.Write("\n Remove Bit : " + n + "-th");
if (value > num)
{
// When after remove bit is not effect to given number
Console.Write("\n Output : " + num + "\n");
return;
}
int result = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
Console.Write("\n Output : " + result + "\n");
}
public static void Main(String[] args)
{
BitManipulation task = new BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
<?php
/*
Php program
Remove nth bit of a number
*/
class BitManipulation
{
// Remove a Bit at given position of a number
public function removeBit($num, $n)
{
if ($n < 1 || $num < 0)
{
return;
}
$value = (1 << ($n - 1));
// Display result
echo "\n Given Number : ". $num;
echo "\n Remove Bit : ". $n ."-th";
if ($value > $num)
{
// When after remove bit is not effect to given number
echo "\n Output : ". $num ."\n";
return;
}
$result = $num;
if (($result ^ $value) != 0)
{
// Deactivation of a removal bit
$result = $result ^ $value;
}
$value = ($value - 1);
// Get the left portion
$value = $result & $value;
// unset all bit in left part
$result = $result - $value;
// Shift by one of left part
$value = $value << 1;
// Add new left part into result
$result = $result | $value;
// Shift right by one bit
$result = $result >> 1;
echo "\n Output : ". $result ."\n";
}
}
function main()
{
$task = new BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
$task->removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
$task->removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
$task->removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
$task->removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
$task->removeBit(6, 1);
}
main();
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
/*
Node Js program
Remove nth bit of a number
*/
class BitManipulation
{
// Remove a Bit at given position of a number
removeBit(num, n)
{
if (n < 1 || num < 0)
{
return;
}
var value = (1 << (n - 1));
// Display result
process.stdout.write("\n Given Number : " + num);
process.stdout.write("\n Remove Bit : " + n + "-th");
if (value > num)
{
// When after remove bit is not effect to given number
process.stdout.write("\n Output : " + num + "\n");
return;
}
var result = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
process.stdout.write("\n Output : " + result + "\n");
}
}
function main()
{
var task = new BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
main();
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
# Python 3 program
# Remove nth bit of a number
class BitManipulation :
# Remove a Bit at given position of a number
def removeBit(self, num, n) :
if (n < 1 or num < 0) :
return
value = (1 << (n - 1))
# Display result
print("\n Given Number : ", num, end = "")
print("\n Remove Bit : ", n ,"-th", end = "")
if (value > num) :
# When after remove bit is not effect to given number
print("\n Output : ", num )
return
result = num
if ((result ^ value) != 0) :
# Deactivation of a removal bit
result = result ^ value
value = (value - 1)
# Get the left portion
value = result & value
# unset all bit in left part
result = result - value
# Shift by one of left part
value = value << 1
# Add new left part into result
result = result | value
# Shift right by one bit
result = result >> 1
print("\n Output : ", result )
def main() :
task = BitManipulation()
# num = 21, position = 3
# 21 = (10101)
# After remove bit at 3rd position
# 9 = (1001)
task.removeBit(21, 3)
# num = 73 position = 5
# 73 => 1001001
# After remove 5-th bit
# (41) 101001
task.removeBit(73, 5)
# num = 80 position = 7
# 73 => 1010000
# After remove 7-th bit
# (16) 10000
task.removeBit(80, 7)
# num = 11 position = 5
# 73 => 01011
# After remove 5-th bit
# (11) 1011
task.removeBit(11, 5)
# num = 6 position = 1
# 6 => 110
# After remove 1-st bit
# (3) 11
task.removeBit(6, 1)
if __name__ == "__main__": main()
Output
Given Number : 21
Remove Bit : 3 -th
Output : 9
Given Number : 73
Remove Bit : 5 -th
Output : 41
Given Number : 80
Remove Bit : 7 -th
Output : 16
Given Number : 11
Remove Bit : 5 -th
Output : 11
Given Number : 6
Remove Bit : 1 -th
Output : 3
# Ruby program
# Remove nth bit of a number
class BitManipulation
# Remove a Bit at given position of a number
def removeBit(num, n)
if (n < 1 || num < 0)
return
end
value = (1 << (n - 1))
# Display result
print("\n Given Number : ", num)
print("\n Remove Bit : ", n ,"-th")
if (value > num)
# When after remove bit is not effect to given number
print("\n Output : ", num ,"\n")
return
end
result = num
if ((result ^ value) != 0)
# Deactivation of a removal bit
result = result ^ value
end
value = (value - 1)
# Get the left portion
value = result & value
# unset all bit in left part
result = result - value
# Shift by one of left part
value = value << 1
# Add new left part into result
result = result | value
# Shift right by one bit
result = result >> 1
print("\n Output : ", result ,"\n")
end
end
def main()
task = BitManipulation.new()
# num = 21, position = 3
# 21 = (10101)
# After remove bit at 3rd position
# 9 = (1001)
task.removeBit(21, 3)
# num = 73 position = 5
# 73 => 1001001
# After remove 5-th bit
# (41) 101001
task.removeBit(73, 5)
# num = 80 position = 7
# 73 => 1010000
# After remove 7-th bit
# (16) 10000
task.removeBit(80, 7)
# num = 11 position = 5
# 73 => 01011
# After remove 5-th bit
# (11) 1011
task.removeBit(11, 5)
# num = 6 position = 1
# 6 => 110
# After remove 1-st bit
# (3) 11
task.removeBit(6, 1)
end
main()
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
/*
Scala program
Remove nth bit of a number
*/
class BitManipulation
{
// Remove a Bit at given position of a number
def removeBit(num: Int, n: Int): Unit = {
if (n < 1 || num < 0)
{
return;
}
var value: Int = (1 << (n - 1));
// Display result
print("\n Given Number : " + num);
print("\n Remove Bit : " + n + "-th");
if (value > num)
{
// When after remove bit is not effect to given number
print("\n Output : " + num + "\n");
return;
}
var result: Int = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
print("\n Output : " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitManipulation = new BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
/*
Swift 4 program
Remove nth bit of a number
*/
class BitManipulation
{
// Remove a Bit at given position of a number
func removeBit(_ num: Int, _ n: Int)
{
if (n < 1 || num < 0)
{
return;
}
var value: Int = (1 << (n - 1));
// Display result
print("\n Given Number : ", num, terminator: "");
print("\n Remove Bit : \(n)-th", terminator: "");
if (value > num)
{
// When after remove bit is not effect to given number
print("\n Output : ", num );
return;
}
var result: Int = num;
if ((result ^ value) != 0)
{
// Deactivation of a removal bit
result = result ^ value;
}
value = (value - 1);
// Get the left portion
value = result & value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value << 1;
// Add new left part into result
result = result | value;
// Shift right by one bit
result = result >> 1;
print("\n Output : ", result );
}
}
func main()
{
let task: BitManipulation = BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
main();
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
/*
Kotlin program
Remove nth bit of a number
*/
class BitManipulation
{
// Remove a Bit at given position of a number
fun removeBit(num: Int, n: Int): Unit
{
if (n < 1 || num < 0)
{
return;
}
var value: Int = (1 shl(n - 1));
// Display result
print("\n Given Number : " + num);
print("\n Remove Bit : " + n + "-th");
if (value > num)
{
// When after remove bit is not effect to given number
print("\n Output : " + num + "\n");
return;
}
var result: Int = num;
if ((result xor value) != 0)
{
// Deactivation of a removal bit
result = result xor value;
}
value = (value - 1);
// Get the left portion
value = result and value;
// unset all bit in left part
result = result - value;
// Shift by one of left part
value = value shl 1;
// Add new left part into result
result = result or value;
// Shift right by one bit
result = result shr 1;
print("\n Output : " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
var task: BitManipulation = BitManipulation();
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9 = (1001)
task.removeBit(21, 3);
// num = 73 position = 5
// 73 => 1001001
// After remove 5-th bit
// (41) 101001
task.removeBit(73, 5);
// num = 80 position = 7
// 73 => 1010000
// After remove 7-th bit
// (16) 10000
task.removeBit(80, 7);
// num = 11 position = 5
// 73 => 01011
// After remove 5-th bit
// (11) 1011
task.removeBit(11, 5);
// num = 6 position = 1
// 6 => 110
// After remove 1-st bit
// (3) 11
task.removeBit(6, 1);
}
Output
Given Number : 21
Remove Bit : 3-th
Output : 9
Given Number : 73
Remove Bit : 5-th
Output : 41
Given Number : 80
Remove Bit : 7-th
Output : 16
Given Number : 11
Remove Bit : 5-th
Output : 11
Given Number : 6
Remove Bit : 1-th
Output : 3
Time Complexity
The time complexity of the given code is O(1) because the algorithm performs a fixed number of bitwise operations,
regardless of the size of the input number num
. The number of iterations or operations in the algorithm
is constant, making it a constant-time operation.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment