Important Practice Problems on Bitwise Algorithm
If we want to set a bit at nth position in the number ‘num’, it can be done using the ‘OR’ operator( | ).
- First, we left shift 1 to n position via (1<<n)
- Then, use the “OR” operator to set the bit at that position. “OR” operator is used because it will set the bit even if the bit is unset previously in the binary representation of the number ‘num’.
Note: If the bit would be already set then it would remain unchanged.
Below is the implementation:
#include <iostream>
using namespace std;
// num is the number and pos is the position
// at which we want to set the bit.
void set(int& num, int pos)
{
// First step is shift '1', second
// step is bitwise OR
num |= (1 << pos);
}
int main()
{
int num = 4, pos = 1;
set(num, pos);
cout << (int)(num) << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 4, pos = 1;
num = set(num, pos);
System.out.println(num);
}
public static int set(int num, int pos)
{
// First step is shift '1', second
// step is bitwise OR
num |= (1 << pos);
return num;
}
}
// This code is contributed by geeky01adash.
# num = number, pos = position at which we want to set the bit
def set(num, pos):
# First step = Shift '1'
# Second step = Bitwise OR
num |= (1 << pos)
print(num)
num, pos = 4, 1
set(num, pos)
# This code is contributed by sarajadhav12052009
using System;
public class GFG {
static public void Main()
{
int num = 4, pos = 1;
set(num, pos);
}
// num = number, pos = position at which we want to set
// the bit
static public void set(int num, int pos)
{
// First Step: Shift '1'
// Second Step: Bitwise OR
num |= (1 << pos);
Console.WriteLine(num);
}
}
// This code is contributed by sarajadhav12052009
<script>
// num is the number and pos is the position
// at which we want to set the bit.
function set(num,pos)
{
// First step is shift '1', second
// step is bitwise OR
num |= (1 << pos);
console.log(parseInt(num));
}
let num = 4;
let pos = 1;
set(num, pos);
// This code is contributed by akashish__
</script>
Output
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Suppose we want to unset a bit at nth position in number ‘num’ then we have to do this with the help of “AND” (&) operator.
- First, we left shift ‘1’ to n position via (1<<n) then we use bitwise NOT operator ‘~’ to unset this shifted ‘1’.
- Now after clearing this left shifted ‘1’ i.e making it to ‘0’ we will ‘AND'(&) with the number ‘num’ that will unset bit at nth position.
Below is the implementation:
#include <iostream>
using namespace std;
// First step is to get a number that has all 1's except
// the given position.
void unset(int& num, int pos)
{
// Second step is to bitwise and this number with given
// number
num &= (~(1 << pos));
}
int main()
{
int num = 7;
int pos = 1;
unset(num, pos);
cout << num << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 7, pos = 1;
num = unset(num, pos);
System.out.println(num);
}
public static int unset(int num, int pos)
{
// Second step is to bitwise and this number with
// given number
num = num & (~(1 << pos));
return num;
}
}
# First Step: Getting which have all '1's except the
# given position
def unset(num, pos):
# Second Step: Bitwise AND this number with the given number
num &= (~(1 << pos))
print(num)
num, pos = 7, 1
unset(num, pos)
using System;
public class GFG {
static public void Main()
{
// First Step: Getting a number which have all '1's
// except the given position
int num = 7, pos = 1;
unset(num, pos);
}
static public void unset(int num, int pos)
{
// Second Step: Bitwise AND this number with the
// given number
num &= (~(1 << pos));
Console.WriteLine(num);
}
}
// First step is to get a number that has all 1's except
// the given position.
function unset(num, pos)
{
// Second step is to bitwise and this number with given
// number
return num &= (~(1 << pos));
}
let num = 7;
let pos = 1;
console.log(unset(num, pos));
// contributed by akashish__
Output
5
Time Complexity: O(1)
Auxiliary Space: O(1)
Toggling means to turn bit ‘on'(1) if it was ‘off'(0) and to turn ‘off'(0) if it was ‘on'(1) previously. We will be using the ‘XOR’ operator here which is this ‘^’. The reason behind the ‘XOR’ operator is because of its properties.
- Properties of ‘XOR’ operator.
- 1^1 = 0
- 0^0 = 0
- 1^0 = 1
- 0^1 = 1
- If two bits are different then the ‘XOR’ operator returns a set bit(1) else it returns an unset bit(0).
Below is the implementation:
#include <iostream>
using namespace std;
// First step is to shift 1,Second step is to XOR with given
// number
void toggle(int& num, int pos) { num ^= (1 << pos); }
int main()
{
int num = 4;
int pos = 1;
toggle(num, pos);
cout << num << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 4, pos = 1;
num = toggle(num, pos);
System.out.println(num);
}
public static int toggle(int num, int pos)
{
// First step is to shift 1,Second step is to XOR
// with given number
num ^= (1 << pos);
return num;
}
}
// This code is contributed by geeky01adash.
def toggle(num, pos):
# First Step: Shifts '1'
# Second Step: XOR num
num ^= (1 << pos)
print(num)
num, pos = 4, 1
toggle(num, pos)
# This code is contributed by sarajadhav12052009
using System;
public class GFG {
static public void Main()
{
int num = 4, pos = 1;
toggle(num, pos);
}
static public void toggle(int num, int pos)
{
// First Step: Shift '1'
// Second Step: XOR num
num ^= (1 << pos);
Console.WriteLine(num);
}
}
// This code is contributed by sarajadhav12052009
// First step is to shift 1,Second step is to XOR with given
// number
function toggle(num, pos){
// First Step: Shifts '1'
// Second Step: XOR num
num ^= (1 << pos)
console.log(num)
}
let num = 4;
let pos = 1;
toggle(num, pos);
// contributed by akashish__
Output
6
Time Complexity: O(1)
Auxiliary Space: O(1)
We used the left shift (<<) operation on 1 to shift the bits to nth position and then use the & operation with number given number, and check if it is not-equals to 0.
Below is the implementation:
#include <iostream>
using namespace std;
bool at_position(int num, int pos)
{
bool bit = num & (1 << pos);
return bit;
}
int main()
{
int num = 5;
int pos = 2;
bool bit = at_position(num, pos);
cout << bit << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 5;
int pos = 0;
int bit = at_position(num, pos);
System.out.println(bit);
}
public static int at_position(int num, int pos)
{
int bit = num & (1 << pos);
return bit;
}
}
# code
def at_position(num, pos):
bit = num & (1 << pos)
return bit
num = 5
pos = 0
bit = at_position(num, pos)
print(bit)
using System;
public class GFG {
public static bool at_position(int num, int pos)
{
int bit = num & (1 << pos);
if (bit == 0)
return false;
return true;
}
static public void Main()
{
int num = 5;
int pos = 2;
bool bit = at_position(num, pos);
Console.WriteLine(bit);
}
}
// This code is contributed by akashish__
<script>
function at_position(num,pos)
{
return num & (1<<pos);
}
let num = 5;
let pos = 0;
console.log(at_position(num, pos));
// contributed by akashish__
</script>
Output
1
Time Complexity: O(1)
Auxiliary Space: O(1)
Below is the implementation:
#include <iostream>
using namespace std;
int main()
{
int num = 12;
int ans = num << 1;
cout << ans << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 12;
int ans = num << 1;
System.out.println(ans);
}
}
// This code is contributed by geeky01adash.
# Python program for the above approach
num = 12
ans = num << 1
print(ans)
# This code is contributed by Shubham Singh
using System;
public class GFG {
static public void Main()
{
int num = 12;
Console.WriteLine(num << 1);
}
}
// This code is contributed by sarajadhav12052009
<script>
// Javascript program for the above approach
var num = 12;
var ans = num<<1;
document.write(ans);
//This code is contributed by Shubham Singh
</script>
Output
24
Time Complexity: O(1)
Auxiliary Space: O(1)
6. Divide a number 2 using the right shift operator
Below is the implementation:
#include <iostream>
using namespace std;
int main()
{
int num = 12;
int ans = num >> 1;
cout << ans << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main(String[] args)
{
int num = 12;
int ans = num >> 1;
System.out.println(ans);
}
}
// This code is contributed by geeky01adash.
# Python program for the above approach
num = 12
ans = num >> 1
print(ans)
# This code is contributed by Shubham Singh
using System;
public class GFG {
static public void Main()
{
int num = 12;
Console.WriteLine(num >> 1);
}
}
// This code is contributed by sarajadhav12052009
<script>
// Javascript program for the above approach
var num = 12;
var ans = num>>1;
document.write(ans);
//This code is contributed by Shubham Singh
</script>
Output
6
Time Complexity: O(1)
Auxiliary Space: O(1)
The problem can be solved based on the following observations:
Say x = n % 4. The XOR value depends on the value if x.
If, x = 0, then the answer is n.
x = 1, then answer is 1.
x = 2, then answer is n+1.
x = 3, then answer is 0.
Below is the implementation of the above approach.
// Direct XOR of all numbers from 1 to n
int computeXOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
else
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Direct XOR of all numbers from 1 to n
public static int computeXOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
else
return 0;
}
public static void main(String[] args) {}
}
// This code is contributed by akashish__
# num = number, pos = position at which we want to set the bit
def set(num, pos):
# First step = Shift '1'
# Second step = Bitwise OR
num |= (1 << pos)
print(num)
num, pos = 4, 1
set(num, pos)
# This code is contributed by sarajadhav12052009
using System;
public class GFG {
// Direct XOR of all numbers from 1 to n
public static int computeXOR(int n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
else
return 0;
}
public static void Main() {}
}
// This code is contributed by akashish__
<script>
// Direct XOR of all numbers from 1 to n
function computeXOR(n)
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
else
return 0;
}
// This code is contributed by Shubham Singh
</script>
Time Complexity: O(1)
Auxiliary Space: O(1)
This can be solved based on the following fact:
If a number N is a power of 2, then the bitwise AND of N and N-1 will be 0. But this will not work if N is 0. So just check these two conditions, if any of these two conditions is true.
Below is the implementation of the above approach.
// Function to check if x is power of 2
bool isPowerOfTwo(int x)
{
// First x in the below expression is
// for the case when x is 0
return x && (!(x & (x - 1)));
}
// Function to check if x is power of 2
public static boolean isPowerOfTwo(int x)
{
// First x in the below expression is
// for the case when x is 0
return x != 0 && ((x & (x - 1)) == 0);
}
# Function to check if x is power of 2
def isPowerOfTwo(x):
# First x in the below expression is
# for the case when x is 0
return x and (not(x & (x - 1)))
# This code is contributed by akashish__
using System;
public class GFG {
// Function to check if x is power of 2
static public bool isPowerOfTwo(int x)
{
// First x in the below expression is
// for the case when x is 0
return (x != 0) && ((x & (x - 1)) == 0);
}
static public void Main() {}
}
// This code is contributed by akashish__
// Function to check if x is power of 2
function isPowerOfTwo(x)
{
// First x in the below expression is
// for the case when x is 0
return x && (!(x & (x - 1)));
}
// contributed by akashish__
Time Complexity: O(1)
Auxiliary Space: O(1)
Counting set bits means, counting total number of 1’s in the binary representation of an integer. For this problem we go through all the bits of given number and check whether it is set or not by performing AND operation (with 1).
Below is the implementation:
// Function to calculate the number of set bits.
int countBits(int n)
{
// Initialising a variable count to 0.
int count = 0;
while (n) {
// If the last bit is 1, count will be incremented
// by 1 in this step.
count += n & 1;
// Using the right shift operator.
// The bits will be shifted one position to the
// right.
n >>= 1;
}
return count;
}
// Function to calculate the number of set bits.
public static int countBits(int n)
{
// Initialising a variable count to 0.
int count = 0;
while (n > 0) {
// If the last bit is 1, count will be incremented
// by 1 in this step.
count += n & 1;
// Using the right shift operator.
// The bits will be shifted one position to the
// right.
n >>= 1;
}
return count;
}
def countBits(n):
# Initializing a variable count to 0
count = 0
while n:
# If the last bit is 1, count will be incremented by 1 in this step.
count += n & 1
# Using the right shift operator. The bits will be shifted one position to the right.
n >>= 1
return count
using System;
public class GFG {
// Function to calculate the number of set bits.
public static int countBits(int n)
{
// Initialising a variable count to 0.
int count = 0;
while (n > 0)
{
// If the last bit is 1, count will be
// incremented by 1 in this step.
count += n & 1;
// Using the right shift operator.
// The bits will be shifted one position to the
// right.
n >>= 1;
}
return count;
}
static public void Main() {}
}
// This code is contributed by akashish__
// Function to calculate the number of set bits.
function countBits(n)
{
// Initialising a variable count to 0.
let count = 0;
while (n) {
// If the last bit is 1, count will be incremented
// by 1 in this step.
count += n & 1;
// Using the right shift operator.
// The bits will be shifted one position to the
// right.
n >>= 1;
}
return count;
}
Time Complexity: O(log(n))
Auxiliary Space: O(1)
The idea is to unset the rightmost bit of number n and XOR the result with n. Then the rightmost set bit in n will be the position of the only set bit in the result. Note that if n is odd, we can directly return 1 as the first bit is always set for odd numbers.
Example:
The number 20 in binary is 00010100, and the position of the rightmost set bit is 3.
00010100 & (n = 20)
00010011 (n-1 = 19)
——————-
00010000 ^ (XOR result number with n)
00010100
——————-
00000100 ——-> rightmost set bit will tell us the position
Below is the implementation:
// Returns the position of the rightmost set bit of `n`
int positionOfRightmostSetBit(int n)
{
// if the number is odd, return 1
if (n & 1) {
return 1;
}
// unset rightmost bit and xor with the number itself
n = n ^ (n & (n - 1));
// find the position of the only set bit in the result;
// we can directly return `log2(n) + 1` from the
// function
int pos = 0;
while (n) {
n = n >> 1;
pos++;
}
return pos;
}
// Returns the position of the rightmost set bit of `n`
public static int positionOfRightmostSetBit(int n)
{
// if the number is odd, return 1
if ((n & 1) != 0) {
return 1;
}
// unset rightmost bit and xor with the number itself
n = n ^ (n & (n - 1));
// find the position of the only set bit in the result;
// we can directly return `log2(n) + 1` from the
// function
int pos = 0;
while (n != 0) {
n = n >> 1;
pos++;
}
return pos;
}
# Returns the position of the rightmost set bit of `n`
def positionOfRightmostSetBit(n):
# if the number is odd, return 1
if n & 1:
return 1
# unset rightmost bit and xor with the number itself
n = n ^ (n & (n - 1))
# find the position of the only set bit in the result;
# we can directly return `log2(n) + 1` from the function
pos = 0
while n:
n = n >> 1
pos = pos + 1
return pos
// Returns the position of the rightmost set bit of `n`
public static int positionOfRightmostSetBit(int n)
{
// if the number is odd, return 1
if ((n & 1) != 0) {
return 1;
}
// unset rightmost bit and xor with the number itself
n = n ^ (n & (n - 1));
// find the position of the only set bit in the result;
// we can directly return `log2(n) + 1` from the
// function
int pos = 0;
while (n != 0) {
n = n >> 1;
pos++;
}
return pos;
}
// Returns the position of the rightmost set bit of `n`
function positionOfRightmostSetBit( n)
{
// if the number is odd, return 1
if (n & 1) {
return 1;
}
// unset rightmost bit and xor with the number itself
n = n ^ (n & (n - 1));
// find the position of the only set bit in the result;
// we can directly return `log2(n) + 1` from the
// function
let pos = 0;
while (n) {
n = n >> 1;
pos++;
}
return pos;
}
Time Complexity: O(log(n))
Auxiliary Space: O(1)
Introduction to Bitwise Algorithms – Data Structures and Algorithms Tutorial
Bit stands for binary digit. A bit is the basic unit of information and can only have one of two possible values that is 0 or 1. In our world, we usually with numbers using the decimal base. In other words. we use the digit 0 to 9 However, there are other number representations that can be quite useful such as the binary number systems.
Unlike humans, computers have no concepts of words and numbers. They receive data encoded at the lowest level as a series of zeros and ones (0 and 1). These are called bits, and they are the basis for all the commands they receive. We’ll begin by learning about bits and then explore a few algorithms for manipulating bits. We’ll then explore a few algorithms for manipulating bits. The tutorial is meant to be an introduction to bit algorithms for programmers.
Table of Content
- What is Bitwise Algorithms?
- Bitwise Operators / Basics of Bit manipulation
- Bitwise AND Operator (&)
- Bitwise OR Operator (|)
- Bitwise XOR Operator (^)
- Bitwise NOT Operator (!~)
- Left-Shift (<<)
- Right-Shift (>>)
- Application of Bit Operators
- Important Practice Problems on Bitwise Algorithm
Contact Us