Mastering the Magic of Bits — In Java

Unlock Efficient Problem-Solving with Clever Tricks Using Bit Manipulation

Photo by Matt Artz on Unsplash

In Java, bitwise operators operate on individual bits of integer data types. These operators are commonly used in low-level programming, bit manipulation, and optimization.

Here is a list of bitwise operators and their explanations along with code examples.

1. Bitwise AND (&)

• Operation: Returns 1 if both corresponding bits are 1, otherwise 0.
• Example:

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary
int result = a & b;  // 0001 in binary (1 in decimal)
System.out.println("Bitwise AND: " + result); 

// Result - Bitwise AND: 1 

2. Bitwise OR (|)

• Operation: Returns 1 if at least one of the corresponding bits is 1.

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary
int result = a | b;  // 0111 in binary (7 in decimal)
System.out.println("Bitwise OR: " + result);

// Bitwise OR: 7

3. Bitwise XOR (^)

• Operation: Returns 1 if corresponding bits are different, otherwise 0.
• XOR of a number with itself is 0.
• XOR of a number with 0 is the number itself.
• The order of XOR operations does not matter.

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary
int result = a ^ b;  // 0110 in binary (6 in decimal)
System.out.println("Bitwise XOR: " + result);

// Bitwise XOR: 6

4. Bitwise Complement (~)

• Operation: Flips all bits (1 → 0 and 0 → 1).
• Note: Operates on a single operand.

int a = 5;  // 0101 in binary
int result = ~a;  // Flips to 1010 in binary (-6 in decimal due to two's complement)
System.out.println("Bitwise Complement: " + result);

// Bitwise Complement: -6

5. Left Shift (<<)

• Operation: Shifts the bits of a number to the left, filling with 0 on the right. Each shift left doubles the value.

int a = 5;  // 0101 in binary
int result = a << 1;  // 1010 in binary (10 in decimal)
System.out.println("Left Shift: " + result);

// Left Shift: 10

6. Right Shift (>>)

• Operation: Shifts the bits of a number to the right, filling with the sign bit (for negative numbers) or 0 (for positive numbers).

int a = 5;  // 0101 in binary
int result = a >> 1;  // 0010 in binary (2 in decimal)
System.out.println("Right Shift: " + result);

// Right Shift: 2

7. Unsigned Right Shift (>>>)

• Operation: Shifts the bits of a number to the right, filling with 0 regardless of the sign bit.

int a = -5;  // In binary: 11111111111111111111111111111011 (32-bit representation)
int result = a >>> 1;  // Shift right and fill with 0
System.out.println("Unsigned Right Shift: " + result);

// Unsigned Right Shift: 2147483645

Additional Notes

1. Negative Numbers: Java uses two’s complement representation for negative numbers, so bitwise operations on negative numbers can yield unexpected results unless carefully analyzed.
2. Applications:

• Setting, clearing, or toggling specific bits.
• Efficient multiplication/division by powers of 2 using << and >>.
• Checking if a number is even/odd using &.

Top Interview Questions

1. Find the Only Non-Repeating Element in an Array

Problem: In an array where every element appears twice except for one, find the unique element.
Hint: XOR cancels out duplicates. Use res ^= num for all elements.

1. Final res = 4, which is the unique number.

2. Check if a Number is a Power of 2

Problem: Determine if a given number is a power of 2.
Hint: A power of 2 has exactly one bit set (e.g., 2 = 10, 4 = 100). Use n & (n - 1) == 0.

3. Count the Number of 1s in the Binary Representation of a Number

Problem: Count how many bits are set to 1 in a number.
Hint: Use n & (n - 1) repeatedly to clear the rightmost set bit. Count the iterations.

4. Reverse the Bits of a 32-Bit Unsigned Integer

Problem: Reverse all the bits in a given 32-bit number.
Hint: Swap bits from opposite ends using bit manipulation and shifting.

5. Find the Missing Number in an Array

Problem: An array of numbers from 0 to n has one missing number. Find it.
Hint: XOR all array elements and numbers 0 to n. The result is the missing number.

6. Add Two Numbers Without Using + or -

Problem: Implement addition using bitwise operators.
Hint: Use a ^ b for addition without carry, and (a & b) << 1 for carry. Repeat until carry is 0.

7. Hamming Distance Between Two Numbers

Problem: Find the number of differing bits between two integers.
Hint: XOR the numbers to identify differing bits, then count the set bits.

8. Find the Two Non-Repeating Elements in an Array

Problem: In an array where all elements appear twice except for two, find the two unique numbers.
Hint: XOR all elements to get x ^ y. Use the rightmost set bit to partition the numbers into two groups.

9. Generate All Subsets of a Set

Problem: Given a set of n elements, generate all its subsets.
Hint: Use a bitmask from 0 to 2^n - 1. Each bitmask represents a subset.

10. Find the Maximum XOR of Two Numbers in an Array

Problem: Find the maximum XOR value for any two numbers in an array.
Hint: Use a trie to store binary representations and find the best complement for each number.