Posted on by Kalkicode
Code Bit Logic

# 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

1. The function `removeBit(num, n)` takes the number `num` and the position `n` of the bit to be removed as inputs.
2. We first check if the value of `n` is less than 1 or if `num` is negative. If either condition is true, we return from the function since it's not possible to remove a bit in these cases.
3. We calculate the value of `1` left-shifted by `(n - 1)` positions, which will set the nth bit to `1` and all other bits to `0`.
4. 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 number `num`.
5. If the calculated value is not greater than `num`, we proceed to remove the nth bit.
6. We use bitwise XOR operation (`^`) to deactivate the nth bit, effectively setting it to `0` while keeping other bits unchanged.
7. We subtract `1` from the calculated value, which will result in all `1`s from the nth position (inclusive) to the rightmost bit (inclusive).
8. 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.
9. We update the `result` by subtracting the calculated value, effectively removing the nth bit.
10. 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.
11. We use bitwise OR operation (`|`) with the result to add the new left portion obtained from the previous step.
12. 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.
13. 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` and `n = 3`, the output is `9`. The binary representation of `21` is `10101`, and after removing the 3rd bit, we get `1001`, which is `9` in decimal.
• For `num = 73` and `n = 5`, the output is `41`. The binary representation of `73` is `1001001`, and after removing the 5th bit, we get `101001`, which is `41` in decimal.
• For `num = 80` and `n = 7`, the output is `16`. The binary representation of `80` is `1010000`, and after removing the 7th bit, we get `10000`, which is `16` in decimal.
• For `num = 11` and `n = 5`, the output is `11`. The binary representation of `11` is `01011`, and after removing the 5th bit, we get `1011`, which is `11` in decimal.
• For `num = 6` and `n = 1`, the output is `3`. The binary representation of `6` is `110`, and after removing the 1st bit, we get `11`, which is `3` 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)
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
}``````

#### 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()
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
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)
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
}``````

#### 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()
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
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()
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
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() :
#  num = 21, position = 3
#  21 = (10101)
#  After remove bit at 3rd position
#  9  = (1001)
#  num = 73  position = 5
#  73 => 1001001
#  After remove 5-th bit
#  (41)   101001
#  num = 80  position = 7
#  73 => 1010000
#  After remove 7-th bit
#  (16)   10000
#  num = 11  position = 5
#  73 => 01011
#  After remove 5-th bit
#  (11)   1011
#  num = 6  position = 1
#  6 => 110
#  After remove 1-st bit
#  (3)   11

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()
#  num = 21, position = 3
#  21 = (10101)
#  After remove bit at 3rd position
#  9  = (1001)
#  num = 73  position = 5
#  73 => 1001001
#  After remove 5-th bit
#  (41)   101001
#  num = 80  position = 7
#  73 => 1010000
#  After remove 7-th bit
#  (16)   10000
#  num = 11  position = 5
#  73 => 01011
#  After remove 5-th bit
#  (11)   1011
#  num = 6  position = 1
#  6 => 110
#  After remove 1-st bit
#  (3)   11
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)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
}``````

#### 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()
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}
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
{
// num = 21, position = 3
// 21 = (10101)
// After remove bit at 3rd position
// 9  = (1001)
// num = 73  position = 5
// 73 => 1001001
// After remove 5-th bit
// (41)   101001
// num = 80  position = 7
// 73 => 1010000
// After remove 7-th bit
// (16)   10000
// num = 11  position = 5
// 73 => 01011
// After remove 5-th bit
// (11)   1011
// num = 6  position = 1
// 6 => 110
// After remove 1-st bit
// (3)   11
}``````

#### 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.

## Comment

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.

Categories
Relative Post