Useful Bitwise Tricks for Competitive Programming
This can be done by left-shifting the value 1 by ‘pos‘ positions (1<< pos) and performing a bitwise OR operation with number n. This operation effectively turns on the bit at the specified position.
// n=number
// pos=It is the position at which we want to set the bit
void set(int & n, int pos)
{
n |= (1 << pos);
}
public class GFG {
// Function to set a bit at a given position
// in a number
static int setBit(int n, int pos)
{
return n | (1 << pos);
}
}
# n = number
# pos = It is the position at which we want to set the bit
def set_bit(n, pos):
n |= (1 << pos)
// Function to set a bit at the specified position in an
// integer n: reference to the number pos: the position at
// which the bit should be set
static void Set(ref int n, int pos)
{
// Use bitwise left shift (1 << pos) to create a mask
// with a 1 at the specified position Use bitwise OR
// assignment (|=) to set the bit at the specified
// position in the number
n |= (1 << pos);
}
// n = number
// pos = It is the position at which we want to set the bit
function set(n, pos) {
n |= (1 << pos);
}
//this code is contributed by Adarsh
This can be done by left-shifting the value 1 by pos positions (1<< pos) and then use bitwise NOT operator ‘~’ to unset this shifted 1, making the bit at position pos to 0 and then use Bitwise AND with the number n that will unset bit at desired positoon of number n.
#include <iostream>
// Unset (clear) a bit at position pos in number n
void unset(int &n, int pos) {
n &= ~(1 << pos);
}
int main() {
int n = 15; // 1111 in binary
int pos = 1;
unset(n, pos); // Should change n to 13, which is 1101 in binary
std::cout << n << std::endl; // Output should be 13
return 0;
}
public class UnsetBit {
// Unset (clear) a bit at position pos in number n
public static int unset(int n, int pos) {
n &= ~(1 << pos);
return n;
}
public static void main(String[] args) {
int n = 15; // 1111 in binary
int pos = 1;
n = unset(n, pos); // Should change n to 13, which is 1101 in binary
System.out.println(n); // Output should be 13
}
}
def unset(n, pos):
n &= ~(1 << pos)
return n
# Example usage
n = 15 # 1111 in binary
pos = 1
n = unset(n, pos) # Should change n to 13, which is 1101 in binary
print(n) # Output should be 13
function unset(n, pos) {
n &= ~(1 << pos);
return n;
}
// Example usage
let n = 15; // 1111 in binary
let pos = 1;
n = unset(n, pos); // Should change n to 13, which is 1101 in binary
console.log(n); // Output should be 13
Use the bitwise XOR (^) operator to toggle (flip) the bit at the given position. If the bit is 0, it becomes 1, and if it’s 1, it becomes 0.
// Flip (toggle) a bit at position pos in number n
void flip(int &n, int pos) {
n ^= (1 << pos);
}
// Flip (toggle) a bit at position pos in number n
static void flip(int[] n, int pos) {
n[0] ^= (1 << pos);
}
# Flip (toggle) a bit at position pos in number n
def flip_bit(n, pos):
n ^= (1 << pos)
// Flip (toggle) a bit at position pos in number n
function flip(n, pos) {
n ^= (1 << pos);
return n;
}
This can be done by performing a bitwise AND operation with a mask having only that bit set. If the result is non-zero, the bit is set; otherwise, it’s unset.
// Check if the bit at position pos in number n is set (1) or unset (0)
bool isBitSet(int n, int pos) {
return ((n & (1 << pos)) != 0);
}
static boolean isBitSet(int n, int pos) {
return ((n & (1 << pos)) != 0);
}
//This code is contributed by Kishan.
# Check if the bit at position pos in number n is set (1) or unset (0)
def is_bit_set(n, pos):
return (n & (1 << pos)) != 0
A power of two is a number with only one bit set in its binary representation, while the number just before it has that bit unset and all the following bits set. Consequently, when you perform a bitwise AND operation between a number and its predecessor, the result will always be 0.
// Check if n is a power of two
bool isPowerOfTwo(int n) {
return ((n & (n - 1)) == 0);
}
public class Main {
// Check if n is a power of two
public static boolean isPowerOfTwo(int n) {
return (n != 0) && ((n & (n - 1)) == 0);
}
}
# Check if n is a power of two
def is_power_of_two(n):
return (n & (n - 1)) == 0
Bit Manipulation for Competitive Programming
Bit manipulation is a technique in competitive programming that involves the manipulation of individual bits in binary representations of numbers. It is a valuable technique in competitive programming because it allows you to solve problems efficiently, often reducing time complexity and memory usage.
Table of Content
- Bitwise Operators
- Useful Bitwise Tricks for Competitive Programming
- Prefix Sum and Bit Manipulation Technique
- Useful Bitwise Equations
- How to solve Bit Manipulation Problems?
- Practice Problems on Bit Manipulation