Bit Manipulation Hacks with Right Shift Operator
Bitwise right shift (>>) is a fundamental operation in bit manipulation and bit twiddling hacks. It is often used in combination with other bitwise operators to achieve various tasks efficiently. Here are some common bit manipulation and bit twiddling hacks that involve bitwise right shift:
1. Setting or Clearing Bits:
In set_bit, the bitwise OR operation (|) with (1 << n) sets the nth bit of the number to 1. In clear_bit, the bitwise AND operation (&) with the complement of (1 << n) clears the nth bit of the number.
#include <stdio.h>
// Setting the nth bit of a number
unsigned int set_bit(unsigned int num, int n) {
return num | (1 << n);
}
// Clearing the nth bit of a number
unsigned int clear_bit(unsigned int num, int n) {
return num & ~(1 << n);
}
int main() {
unsigned int num = 10; // Binary: 1010
printf("Set bit at position 2: %u\n", set_bit(num, 2)); // Output: 14 (Binary: 1110)
printf("Clear bit at position 3: %u\n", clear_bit(num, 3)); // Output: 2 (Binary: 0010)
return 0;
}
Output
Set bit at position 2: 14 Clear bit at position 3: 2
2. Checking if a Number is a Power of 2:
A number is a power of 2 if it has only one bit set. The expression (num & (num - 1)) clears the lowest set bit, so if the result is zero and the number is not zero, then it is a power of 2.
#include <stdio.h>
#include <stdbool.h>
// Checking if a number is a power of 2
bool is_power_of_2(unsigned int num) {
return (num != 0) && ((num & (num - 1)) == 0);
}
int main() {
unsigned int num = 16; // Binary: 10000
printf("%d\n", is_power_of_2(num)); // Output: true (1)
return 0;
}
Output
1
3. Counting Set Bits (Population Count):
The loop iterates through each bit of the number and counts the bits that are set to 1 using the bitwise AND operation (&) with 1.
#include <stdio.h>
// Counting the number of set bits in a number
int count_set_bits(unsigned int num) {
int count = 0;
while (num) {
count += num & 1;
num >>= 1;
}
return count;
}
int main() {
unsigned int num = 15; // Binary: 1111
printf("Number of set bits: %d\n", count_set_bits(num)); // Output: 4
return 0;
}
Output
Number of set bits: 4
4. Extracting the Lowest Set Bit:
The expression num & -num isolates the lowest set bit of the number by preserving only that bit and setting all other bits to 0.
#include <stdio.h>
// Extracting the lowest set bit of a number
unsigned int extract_lowest_set_bit(unsigned int num) {
return num & -num;
}
int main() {
unsigned int num = 14; // Binary: 1110
printf("Lowest set bit: %u\n", extract_lowest_set_bit(num)); // Output: 2 (Binary: 0010)
return 0;
}
Output
Lowest set bit: 2
5. Rotating Bits:
The expression (num >> n) | (num << (sizeof(num) * 8 - n)) rotates the bits of the number to the right by n positions.
#include <stdio.h>
// Rotating bits to the right by n positions
unsigned int rotate_right(unsigned int num, int n) {
return (num >> n) | (num << (sizeof(num) * 8 - n));
}
int main() {
unsigned int num = 10; // Binary: 1010
printf("Rotated right by 2 positions: %u\n", rotate_right(num, 2)); // Output: 40 (Binary: 101000)
return 0;
}
Output
Rotated right by 2 positions: 2147483650
6. Reversing Bits:
The loop iterates through each bit of the number, shifting and adding the bits to the reversed number to reverse them.
#include <iostream>
// Reversing the bits of a number
unsigned int reverseBits(unsigned int num)
{
unsigned int reversedNum = 0;
while (num) {
reversedNum <<= 1;
reversedNum |= num & 1;
num >>= 1;
}
return reversedNum;
}
int main()
{
unsigned int num = 10; // Binary: 1010
std::cout << "Reversed bits: " << reverseBits(num)
<< std::endl; // Output: 5 (Binary: 0101)
return 0;
}
#include <stdio.h>
// Reversing the bits of a number
unsigned int reverse_bits(unsigned int num)
{
unsigned int reversed_num = 0;
while (num) {
reversed_num <<= 1;
reversed_num |= num & 1;
num >>= 1;
}
return reversed_num;
}
int main()
{
unsigned int num = 10; // Binary: 1010
printf("Reversed bits: %u\n",
reverse_bits(num)); // Output: 5 (Binary: 0101)
return 0;
}
public class Main {
// Function to reverse the bits of a number
static int reverseBits(int num)
{
int reversedNum = 0;
while (num != 0) {
// Shift the reversed number left by 1 position
reversedNum <<= 1;
// Add the least significant bit of num to
// reversedNum
reversedNum |= num & 1;
// Shift num right by 1 position
num >>= 1;
}
return reversedNum;
}
public static void main(String[] args)
{
int num = 10; // Binary: 1010
System.out.println(
"Reversed bits: "
+ reverseBits(num)); // Output: 5 (Binary: 0101)
}
}
# Reversing the bits of a number
def reverse_bits(num):
reversed_num = 0
while num:
reversed_num <<= 1
reversed_num |= num & 1
num >>= 1
return reversed_num
def main():
num = 10 # Binary: 1010
print("Reversed bits:", reverse_bits(num)) # Output: 5 (Binary: 0101)
if __name__ == "__main__":
main()
function reverseBits(num) {
let reversedNum = 0;
while (num !== 0) {
// Shift the reversed number left by 1 position
reversedNum <<= 1;
// Add the least significant bit of num to reversedNum
reversedNum |= num & 1;
// Shift num right by 1 position
num >>= 1;
}
return reversedNum;
}
// Test the function
let num = 10; // Binary: 1010
console.log("Reversed bits: " + reverseBits(num)); // Output: 5 (Binary: 0101)
Output
Reversed bits: 5
Right Shift Operator (>>) in Programming
Right shift operator (>>), commonly found in programming languages, including C, C++, Java, and others, is used to shift the bits of a number to the right by a specified number of positions. Each shift moves all bits in the operand to the right by the number of positions indicated by the right operand.
Table of Content
- Right Shift Operator (>>) Definition
- Right Shift Operator (>>) Syntax
- Right Shift Operator (>>) Examples
- Right Shift Operator (>>) with Signed Integers
- Right Shift Operator (>>) with Unsigned Integers
- Right Shift Operator (>>) with Signed vs. Unsigned Integers
- Logical Right Shift
- Arithmetic Right Shift
- Logical Right Shift vs. Arithmetic Right Shift
- Right Shift Operator (>>) Optimization Techniques
- Bit Manipulation Hacks with Right Shift Operator
This comprehensive guide aims to provide a deep understanding of bitwise right shift operators, from the foundational principles to advanced optimization strategies.
Contact Us