Okay, I can help you with that! I will process the “Bit_Manipulations_leetcode.

pdf” file, extract the core

patterns and examples, convert those examples to Java, and then enrich the content with detailed notes, BitSet
patterns, and other useful bit manipulation tricks.

First, I need to read the content of the PDF.

Okay, I’ve processed the content of the “Bit_Manipulations_leetcode.pdf”. I will now provide a rewritten and

enhanced version, focusing on patterns, Java examples, detailed notes, BitSet patterns, and additional tricks,

while removing unnecessary fluff.

### Mastering Bit Manipulation: Patterns, Tricks, and Java

Examples
Bit manipulation is a powerful technique for writing highly efficient code, especially crucial in competitive

programming and performance-sensitive applications. By operating directly on the binary representations of

numbers, we can achieve significant speedups and often solve problems with elegant, concise solutions. This
guide covers fundamental bitwise operators, common patterns, Java’s BitSet class, and advanced tricks.

#### Part 1: Basic Bitwise Operators in Java

Java provides the following bitwise operators:

1. Bitwise AND ( & ):

Operation: A binary operator that compares each bit of its first operand to the
corresponding bit of its second operand. If both bits are 1, the corresponding result bit is set to

1. Otherwise, the corresponding result bit is set to 0.

Example: 5 & 3 (binary 0101 & 0011 ) results in 1 (binary 0001 ).

Use Case: Often used to check if a particular bit is set or to clear bits (masking).

2. Bitwise OR ( | ):

Operation: A binary operator that compares each bit of its first operand to the
corresponding bit of its second operand. If either bit is 1, the corresponding result bit is set to

1. Otherwise, the corresponding result bit is set to 0.

Example: 5 | 3 (binary 0101 | 0011 ) results in 7 (binary 0111 ).

Use Case: Often used to set particular bits.

3. Bitwise XOR ( ^ ):

Operation: A binary operator that compares each bit of its first operand to the
corresponding bit of its second operand. If the bits are different, the corresponding result bit

is set to 1. If the bits are the same, the corresponding result bit is set to 0.

Example: 5 ^ 3 (binary 0101 ^ 0011 ) results in 6 (binary 0110 ).

Properties:

x ^ 0 = x

x ^ x = 0
x ^ y = y ^ x (Commutative)

(x ^ y) ^ z = x ^ (y ^ z) (Associative)
Use Case: Swapping numbers, finding the element that appears an odd number of times,

flipping bits.

4. Bitwise NOT ( ~ ) / Complement:

Operation: A unary operator that inverts all the bits of its operand. Each 1 becomes a 0, and
each 0 becomes a 1.
Example: ~5 (binary ~...00000101 ) results in ...11111010 (which is -6 in two’s

complement representation for an int ).

Use Case: Creating masks, flipping all bits.

5. Left Shift ( << ):

Operation: A binary operator that shifts the bits of the first operand to the left by the

number of positions specified by the second operand. Vacated bits on the right are filled with
zeros.
Example: 5 << 2 (binary 0101 << 2 ) results in 20 (binary 00010100 ).
Mathematical Equivalent: x << n is equivalent to x * 2^n .

Note: The shift count is effectively n % 32 for int and n % 64 for long .

6. Signed Right Shift ( >> ):

Operation: A binary operator that shifts the bits of the first operand to the right by the
number of positions specified by the second operand. For positive numbers, vacated bits on

the left are filled with zeros. For negative numbers (in two’s complement), vacated bits on the
left are filled with 1s to preserve the sign (sign extension).
Example:

20 >> 2 (binary 00010100 >> 2 ) results in 5 (binary 00000101 ).

 -20 >> 2 (binary ...11101100 >> 2 ) results in -5 (binary ...11111011 ).

Mathematical Equivalent: x >> n is roughly equivalent to x / 2^n (flooring towards

negative infinity for negative numbers).

7. Unsigned Right Shift ( >>> ):

Operation: A binary operator that shifts the bits of the first operand to the right by the
number of positions specified by the second operand. Vacated bits on the left are always filled

with zeros, regardless of the sign of the number.

Example:

20 >>> 2 (binary 00010100 >>> 2 ) results in 5 (binary 00000101 ).

-20 >>> 2 (binary 11111111111111111111111111101100 >>> 2 for a 32-

bit int) results in 1073741819 (binary
00111111111111111111111111111011 ).

Use Case: Useful when you need to treat a number as an unsigned bit pattern, especially
when dealing with negative numbers where sign extension is not desired.

Important Note on Bit Indexing: Throughout this guide, bit positions are generally referred to using 0-

based indexing, where bit 0 is the least significant bit (LSB) or the rightmost bit.

#### Part 2: Core Bit Manipulation Patterns and Tricks

Here are common bit manipulation patterns with Java examples and detailed explanations. All these typically
have a time complexity of O(1) unless otherwise stated.

1. Multiplication by a Power of 2

Pattern: num << k (Multiplies num by 2^k )

Java Example:

int num = 5; // Binary: 0101

int k = 2;

int result = num << k; // 5 * 2^2 = 5 * 4 = 20

// result is 20 (Binary: 00010100)

System.out.println(num + " * 2^" + k + " = " + result);

Detailed Notes:

Left-shifting a number by k positions is equivalent to multiplying it by 2^k .

 Each left shift moves all bits one position to the left and fills the LSB with 0.

This is significantly faster than traditional multiplication when multiplying by powers of two.

2. Division by a Power of 2

Pattern: num >> k (Divides num by 2^k , integer division)

Java Example:

int num = 20; // Binary: 00010100

int k = 2;

int result = num >> k; // 20 / 2^2 = 20 / 4 = 5

// result is 5 (Binary: 00000101)

System.out.println(num + " / 2^" + k + " = " + result);

int negativeNum = -20;

int resultNegative = negativeNum >> k; // -20 / 4 = -5

System.out.println(negativeNum + " / 2^" + k + " = " + resultNegative);

Detailed Notes:

Right-shifting a number by k positions is equivalent to dividing it by 2^k and truncating

towards negative infinity (for signed right shift >> ).

Each right shift moves all bits one position to the right. The MSB is filled based on the sign for

>> (sign extension) or with 0 for >>> .

Faster than traditional division when dividing by powers of two.

3. Check if a Number is Odd or Even

Pattern: (num & 1) == 0 for even, (num & 1) == 1 for odd.

Java Example:

int num = 9; // Binary: 1001

if ((num & 1) == 0) {

System.out.println(num + " is Even");

} else {

System.out.println(num + " is Odd"); // Output

num = 10; // Binary: 1010

if ((num & 1) == 0) {
 System.out.println(num + " is Even"); // Output

} else {

System.out.println(num + " is Odd");

}

Detailed Notes:

An odd number always has its LSB (bit 0) set to 1. An even number always has its LSB set to 0.

num & 1 isolates the LSB. If it’s 1, the number is odd; if it’s 0, the number is even.

4. Swap Two Numbers using XOR

Pattern:

a = a ^ b;

b = a ^ b;

a = a ^ b;

Java Example:

int a = 5; // Binary: 0101

int b = 10; // Binary: 1010

System.out.println("Before swap: a = " + a + ", b = " + b);

a = a ^ b; // a = 5 ^ 10 = 15 (1111)

b = a ^ b; // b = 15 ^ 10 = 5 (0101)
a = a ^ b; // a = 15 ^ 5 = 10 (1010)

System.out.println("After swap: a = " + a + ", b = " + b);

Detailed Notes:

How it works:

1. a = a ^ b : a now stores a_original ^ b_original .

2. b = a ^ b : b becomes (a_original ^ b_original) ^ b_original .

Since x ^ x = 0 and x ^ 0 = x , this simplifies to b = a_original .

3. a = a ^ b : a becomes (a_original ^ b_original) ^ a_original .

This simplifies to a = b_original .

Caveats:

Does not use a temporary variable.

Important: If a and b refer to the same memory location (e.g., swapping an array
element with itself using indices i and j where i == j ), this method will result
 in a becoming 0 because a = a ^ a is the first step.
On modern CPUs with advanced pipelining and register renaming, the traditional

swap with a temporary variable might sometimes be faster or equally fast due to

instruction-level parallelism. Readability often favors the temporary variable method.

5. Check if the i-th Bit is Set (0-indexed)

Pattern: (num & (1 << i)) != 0

Java Example:

int num = 10; // Binary: 1010

int i = 1; // Check the 1st bit (0-indexed, value is 0)

// 1 << i creates a mask with only the i-th bit set (e.g., 1 << 1 is 001
0)

if ((num & (1 << i)) != 0) {

System.out.println("Bit " + i + " of " + num + " is set (1).");
} else {

System.out.println("Bit " + i + " of " + num + " is not set (0).");

// Output for i=1 (010)
}

i = 3; // Check the 3rd bit (value is 1)

if ((num & (1 << i)) != 0) {

System.out.println("Bit " + i + " of " + num + " is set (1)."); // O

utput for i=3 (1000)
} else {

System.out.println("Bit " + i + " of " + num + " is not set (0).");

}

Detailed Notes:

1 << i creates a mask with only the i -th bit set to 1 (e.g., if i=2 , mask is 0100 ).
Performing num & mask will result in a non-zero value if the i -th bit in num is also 1.

Otherwise, it will be 0.
Remember that i is 0-indexed (0 for LSB, 1 for the next bit, and so on).

6. Set (Turn On) the i-th Bit (0-indexed)

Pattern: num | (1 << i)

 Java Example:

int num = 10; // Binary: 1010

int i = 0; // Set the 0th bit

// 1 << i creates a mask with only the i-th bit set (e.g., 1 << 0 is 000
1)
int result = num | (1 << i); // 1010 | 0001 = 1011 (11)

System.out.println("Original: " + Integer.toBinaryString(num) +

", After setting bit " + i + ": " + Integer.toBinaryS
tring(result) +

" (" + result + ")");

Detailed Notes:

1 << i creates a mask with the i -th bit as 1.

ORing num with this mask sets the i -th bit in num to 1, leaving other bits unchanged (since
x | 0 = x and x | 1 = 1 ).

7. Clear (Turn Off) the i-th Bit (0-indexed)

Pattern: num & ~(1 << i)

Java Example:

int num = 10; // Binary: 1010

int i = 1; // Clear the 1st bit

// 1 << i creates a mask like 0010
// ~(1 << i) creates a mask like ...11111101 (all 1s except at i-th posi

tion)
int result = num & ~(1 << i); // 1010 & 1101 = 1000 (8)
System.out.println("Original: " + Integer.toBinaryString(num) +

", After clearing bit " + i + ": " + Integer.toBinary

String(result) +
" (" + result + ")");

Detailed Notes:

1 << i creates a mask with the i -th bit as 1.

~(1 << i) inverts this mask, resulting in a mask where all bits are 1 except for the i -th

bit, which is 0.
 ANDing num with this inverted mask clears the i -th bit in num (since x & 1 = x and x
& 0 = 0 ), leaving other bits unchanged.

8. Flip (Toggle) the i-th Bit (0-indexed)

Pattern: num ^ (1 << i)

Java Example:

int num = 10; // Binary: 1010

int i = 1; // Flip the 1st bit (from 0 to 1)

int result = num ^ (1 << i); // 1010 ^ 0010 = 1000 (8) -> Error in origi
nal example, should be 1010 ^ 0010 = 1000
// Correct: 10 (1010), i=1 (0-indexed, bit

is 1). Mask is 0010.

// 1010 ^ 0010 = 1000 (8). Bit 1 was 1, flip
ped to 0.

System.out.println("Original: " + Integer.toBinaryString(num) +

", After flipping bit " + i + ": " + Integer.toBinaryS
tring(result) +

" (" + result + ")");

num = 10; // Binary: 1010

i = 0; // Flip the 0th bit (from 0 to 1)

result = num ^ (1 << i); // 1010 ^ 0001 = 1011 (11)
System.out.println("Original: " + Integer.toBinaryString(num) +

", After flipping bit " + i + ": " + Integer.toBinaryS

tring(result) +
" (" + result + ")");

Detailed Notes:

1 << i creates a mask with the i -th bit as 1.

XORing num with this mask flips the i -th bit in num (since x ^ 0 = x and x ^ 1 =
~x ), leaving other bits unchanged.

9. Check if a Number is a Power of 2

Pattern: (num > 0) && (num & (num - 1)) == 0

Java Example:
 int num = 16; // Binary: 10000
if ((num > 0) && (num & (num - 1)) == 0) {

System.out.println(num + " is a power of 2."); // Output

} else {
System.out.println(num + " is not a power of 2.");

num = 15; // Binary: 01111

if ((num > 0) && (num & (num - 1)) == 0) {

System.out.println(num + " is a power of 2.");
} else {

System.out.println(num + " is not a power of 2."); // Output

}

Detailed Notes:

A positive number that is a power of 2 has exactly one bit set in its binary representation (e.g.,
1, 2, 4, 8, 16 are 0001 , 0010 , 0100 , 1000 , 10000 ).

Subtracting 1 from a power of 2 (e.g., n ) flips all the bits to the right of the set bit, including
the set bit itself. For example, 16 (10000) minus 1 is 15 (01111) .
So, n & (n - 1) will be 0 if n is a power of 2 (because there will be no common set bits).

The num > 0 check is important because 0 & (0 - 1) would also be 0 , but 0 is not
considered a power of 2.

10. Convert Uppercase Char to Lowercase Char

Pattern: char_val | ' ' (ASCII space, which is 32)

Java Example:

char upper = 'A'; // ASCII 65 (Binary ...01000001)

// ASCII of ' ' (space) is 32 (Binary ...00100000)

// The 5th bit (0-indexed) distinguishes uppercase from lowercase for En

glish letters.
// 'A' (01000001) | ' ' (00100000) = 'a' (01100001, ASCII 97)

char lower = (char) (upper | ' ');

System.out.println(upper + " -> " + lower); // Output: A -> a

Detailed Notes:

The ASCII values of lowercase letters are exactly 32 greater than their uppercase counterparts.
 ASCII 32 is a space ' ' . Its binary representation has the 5th bit (0-indexed) set
( 00100000 ).

Uppercase letters have the 5th bit as 0. ORing with ' ' sets this 5th bit to 1, converting it to
lowercase.
This works for English alphabet characters where this specific bit difference holds.

11. Convert Lowercase Char to Uppercase Char

Pattern: char_val & '_' (ASCII underscore, which is 95, or ~' ' effectively for the relevant
bit)

Alternatively and more robustly: char_val & ~(' ') or char_val & ~32
Java Example:

char lower = 'a'; // ASCII 97 (Binary ...01100001)

// To convert to uppercase, we need to clear the 5th bit.

// Mask to clear 5th bit: ~(' ') which is ~(00100000) = ...11011111

// 'a' (01100001) & (...11011111) = 'A' (01000001, ASCII 65)
char upper = (char) (lower & ~' '); // or (char) (lower & '_') if '_' is

used carefully
System.out.println(lower + " -> " + upper); // Output: a -> A

// The original document suggests `ch & '_'`. ASCII of '_' is 95 (010111
11).
// 'a' (01100001) & '_' (01011111) = 01000001 ('A'). This works.

// The key is that '_' has the 5th bit as 0, and other relevant bits as
1.

Detailed Notes:

To convert lowercase to uppercase, we need to clear the 5th bit (0-indexed).

~' ' (or ~32 ) creates a mask ...11011111 which, when ANDed, clears the 5th bit.

Using '_' (ASCII 95, binary 01011111 ) also works because its 5th bit is 0. ANDing with it
clears the 5th bit of the lowercase character.

12. Toggle Case of a Character (Upper to Lower, Lower to Upper)

Pattern: char_val ^ ' ' (or char_val ^ 32 )

Java Example:
 char letter1 = 'A'; // Uppercase

char toggled1 = (char) (letter1 ^ ' '); // 'A' ^ 32 = 'a'

System.out.println(letter1 + " -> " + toggled1);

char letter2 = 'b'; // Lowercase

char toggled2 = (char) (letter2 ^ ' '); // 'b' ^ 32 = 'B'
System.out.println(letter2 + " -> " + toggled2);

Detailed Notes:

XORing with ' ' (32) flips the 5th bit (0-indexed).

If the 5th bit is 0 (uppercase), it becomes 1 (lowercase).

If the 5th bit is 1 (lowercase), it becomes 0 (uppercase).

13. Count Set Bits (Brian Kernighan’s Algorithm)

Pattern: Loop num &= (num - 1) until num is 0.

Java Example:

int num = 19; // Binary: 10011 (3 set bits)

int count = 0;
int tempNum = num;

while (tempNum > 0) {

tempNum &= (tempNum - 1); // Clears the least significant set bit
count++;

System.out.println("Number of set bits in " + num + " (Kernighan): " + c

ount); // Output: 3

// Java built-in method

System.out.println("Number of set bits in " + num + " (Integer.bitCoun

t): " + Integer.bitCount(num)); // Output: 3

Detailed Notes:

How it works: num - 1 flips all bits to the right of the LSB, including the LSB itself.

For example, if num = 12 (1100) , num - 1 = 11 (1011) .

num & (num - 1) becomes 1100 & 1011 = 1000 . The LSB is cleared.
The loop runs exactly as many times as there are set bits.
 Time Complexity: O(k), where k is the number of set bits. This is efficient for sparse set

bits.

Java Built-in: Integer.bitCount(int n) and Long.bitCount(long n) are highly

optimized (often using hardware instructions) and should be preferred in Java.

14. Count Leading Zeros

Pattern: (Manual approach complex, use built-in)

Java Example:

int num = 16; // Binary for 32-bit int: 00000000000000000000000000010000

// Leading zeros: 27 (assuming 32-bit int, 32 - 5 bits use

d)

System.out.println("Number of leading zeros in " + num + ": " + Integer.

numberOfLeadingZeros(num)); // Output: 27

num = 0; // All bits are zero (except if it's 0 itself)

System.out.println("Number of leading zeros in " + num + ": " + Integer.

numberOfLeadingZeros(num)); // Output: 32

num = -1; // Binary: 1111...1111

System.out.println("Number of leading zeros in " + num + ": " + Integer.

numberOfLeadingZeros(num)); // Output: 0

Detailed Notes:

Counts the number of zero bits preceding the highest-order (“leftmost”) one-bit in the two’s

complement binary representation of the specified int value.

If the value is 0, it returns 32.

Java Built-in: Integer.numberOfLeadingZeros(int n) and

Long.numberOfLeadingZeros(long n) are efficient.

15. Count Trailing Zeros

Pattern: (Manual approach: loop and right shift while LSB is 0, use built-in)
Java Example:

int num = 20; // Binary: ...00010100 (2 trailing zeros)

System.out.println("Number of trailing zeros in " + num + " (Integer.num

berOfTrailingZeros): " + Integer.numberOfTrailingZeros(num)); // Output:

 2

// Manual approach:

int tempNum = num;

int trailingZeros = 0;

if (tempNum == 0) {

trailingZeros = 32; // Or based on data type size

} else {

while ((tempNum & 1) == 0) {

tempNum >>= 1;
trailingZeros++;

}
System.out.println("Number of trailing zeros in " + num + " (Manual): "

+ trailingZeros); // Output: 2

num = 0;

System.out.println("Number of trailing zeros in " + num + " (Integer.num

berOfTrailingZeros): " + Integer.numberOfTrailingZeros(num)); // Output:

32

Detailed Notes:

Counts the number of zero bits following the lowest-order (“rightmost”) one-bit in the two’s

complement binary representation.

If the value is 0, it returns 32.

Java Built-in: Integer.numberOfTrailingZeros(int n) and

Long.numberOfTrailingZeros(long n) are efficient.

16. Find Minimum or Maximum of Two Numbers (Less Common Trick)

Pattern:

min = y ^ ((x ^ y) & -(x < y ? 1 : 0));

max = x ^ ((x ^ y) & -(x < y ? 1 : 0));

(Note: In C/C++, -(x < y) directly gives all 1s or all 0s. Java needs a ternary for the

boolean to int conversion for the negative sign to work as intended for the mask.)
Java Example:

int x = 5, y = 10;

int min, max;

 // If x < y is true, (x < y ? 1 : 0) is 1. Then -(1) is -1 (all bits set
to 1 in 2's complement).

// If x < y is false, (x < y ? 1 : 0) is 0. Then -(0) is 0.

int mask = -(x < y ? 1 : 0); // -1 if x < y, else 0

min = y ^ ((x ^ y) & mask); // If x < y, mask is -1 (all 1s): y ^ (x ^

y) & (~0) = y ^ x ^ y = x
// If x >= y, mask is 0: y ^ ((x ^ y) & 0) =

y ^ 0 = y

max = x ^ ((x ^ y) & mask); // If x < y, mask is -1: x ^ (x ^ y) & (~0)

= x ^ x ^ y = y

// If x >= y, mask is 0: x ^ ((x ^ y) & 0) =

x ^ 0 = x

System.out.println("x=" + x + ", y=" + y);

System.out.println("Min: " + min); // Output: Min: 5

System.out.println("Max: " + max); // Output: Max: 10

Detailed Notes:

This trick avoids branching.

-(x < y ? 1 : 0) creates a mask:

If x < y , -(1) is -1 (all bits are 1s, e.g., 111...111 ).

If x >= y , -(0) is 0 (all bits are 0s, e.g., 000...000 ).

For min :

If x < y (mask is all 1s): min = y ^ ((x ^ y) & -1) = y ^ x ^ y = x .

If x >= y (mask is 0): min = y ^ ((x ^ y) & 0) = y ^ 0 = y .

For max :

If x < y (mask is all 1s): max = x ^ ((x ^ y) & -1) = x ^ x ^ y = y .

If x >= y (mask is 0): max = x ^ ((x ^ y) & 0) = x ^ 0 = x .

Practicality: While clever, standard conditional operators ( x < y ? x : y ) or

Math.min() / Math.max() are generally more readable and often just as performant (or

better) due to modern compiler optimizations and CPU branch prediction. This bitwise trick is

more of an academic curiosity.

#### Part 3: Java BitSet Patterns

The java.util.BitSet class creates a special type of array that holds bit values (booleans). A BitSet is

dynamically sized and can be more memory-efficient than a boolean[] when you have a large number of

bits, especially if they are sparse.

1. Initialization

Java Example:

import java.util.BitSet;

// Creates a BitSet with default initial size

BitSet bs1 = new BitSet();

// Creates a BitSet with a specified initial number of bits

// The BitSet will automatically grow if needed.

BitSet bs2 = new BitSet(64); // Can hold at least 64 bits initially

Detailed Notes:

A BitSet 's size is the number of bits of space currently in use by the BitSet to represent
bit values. The length of a BitSet is the index of the highest set bit plus one.

2. Setting and Clearing Bits

Methods:

set(int bitIndex) : Sets the bit at the specified index to true .

set(int bitIndex, boolean value) : Sets the bit to the given value .
set(int fromIndex, int toIndex) : Sets bits from fromIndex (inclusive) to

toIndex (exclusive) to true .

clear(int bitIndex) : Sets the bit at the specified index to false .

clear(int fromIndex, int toIndex) : Sets bits from fromIndex (inclusive) to

toIndex (exclusive) to false .

clear() : Clears all bits in the BitSet .

Java Example:

BitSet bs = new BitSet();

bs.set(0); // Set bit 0

bs.set(5, true); // Set bit 5

bs.set(10, 15); // Set bits 10, 11, 12, 13, 14
 System.out.println("After set operations: " + bs); // {0, 5, 10, 11, 12,
13, 14}

bs.clear(5); // Clear bit 5

bs.clear(10, 12); // Clear bits 10, 11

System.out.println("After clear operations: " + bs); // {0, 12, 13, 14}

3. Getting Bit Values

Method: get(int bitIndex) : Returns true if the bit is set, false otherwise.

Java Example:

BitSet bs = new BitSet();

bs.set(3);

System.out.println("Bit 3 is set: " + bs.get(3)); // true

System.out.println("Bit 4 is set: " + bs.get(4)); // false

4. Flipping Bits

Method:

flip(int bitIndex) : Reverses the value of the bit at the index.

flip(int fromIndex, int toIndex) : Reverses bits from fromIndex (inclusive) to

toIndex (exclusive).

Java Example:

BitSet bs = new BitSet();

bs.set(1); // {1}
bs.flip(1); // Bit 1 is now false. bs is {}

bs.flip(2); // Bit 2 is now true. bs is {2}

System.out.println("After flip operations: " + bs); // {2}

5. Cardinality (Number of Set Bits)

Method: cardinality() : Returns the number of bits set to true .

Java Example:

BitSet bs = new BitSet();

bs.set(0);

bs.set(10);
 bs.set(100);

System.out.println("Cardinality (set bits): " + bs.cardinality()); // 3

6. Logical Operations

Methods: and(BitSet set) , or(BitSet set) , xor(BitSet set) , andNot(BitSet

set)

Detailed Notes: These perform bitwise logical operations on this BitSet with another

BitSet . The current BitSet is modified.

Java Example:

BitSet bs1 = new BitSet();

bs1.set(0); bs1.set(1); bs1.set(2); // bs1 = {0, 1, 2}

BitSet bs2 = new BitSet();

bs2.set(1); bs2.set(2); bs2.set(3); // bs2 = {1, 2, 3}

BitSet bsAnd = (BitSet) bs1.clone();

bsAnd.and(bs2); // bsAnd = {1, 2} (Intersection)

System.out.println("bs1 AND bs2: " + bsAnd);

BitSet bsOr = (BitSet) bs1.clone();

bsOr.or(bs2); // bsOr = {0, 1, 2, 3} (Union)

System.out.println("bs1 OR bs2: " + bsOr);

BitSet bsXor = (BitSet) bs1.clone();

bsXor.xor(bs2); // bsXor = {0, 3} (Symmetric difference)

System.out.println("bs1 XOR bs2: " + bsXor);

BitSet bsAndNot = (BitSet) bs1.clone();

bsAndNot.andNot(bs2); // bsAndNot = {0} (Elements in bs1 but not in bs2)

System.out.println("bs1 ANDNOT bs2: " + bsAndNot);

7. Iterating Over Set Bits

Methods:

nextSetBit(int fromIndex) : Returns the index of the first bit that is set to true on
or after fromIndex . Returns -1 if no such bit exists.
 nextClearBit(int fromIndex) : Returns the index of the first bit that is false on or

after fromIndex .

previousSetBit(int fromIndex) : Returns index of nearest bit set to true on or

before fromIndex .

previousClearBit(int fromIndex) : Returns index of nearest bit set to false on or

before fromIndex .
Java Example:

BitSet bs = new BitSet();

bs.set(2); bs.set(5); bs.set(10);

System.out.print("Set bits are: ");

for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {

System.out.print(i + " "); // Output: 2 5 10

if (i == Integer.MAX_VALUE) { // Avoid infinite loop with nextSetBit

(Integer.MAX_VALUE + 1)
break;

}
System.out.println();

8. Length and Size

Methods:

length() : Returns the “logical size” of the BitSet : the index of the highest set bit plus
one. Returns 0 if the BitSet contains no set bits.

size() : Returns the number of bits of space actually in use by this BitSet to represent

bit values (typically a multiple of 64).

Java Example:

BitSet bs = new BitSet();

bs.set(63);

System.out.println("Length: " + bs.length()); // 64

System.out.println("Size: " + bs.size()); // Likely 64 or more

bs.set(100);
System.out.println("Length: " + bs.length()); // 101

System.out.println("Size: " + bs.size()); // Likely 128 or more

Use Cases for BitSet :

Representing a set of boolean flags efficiently.

Implementing Sieve of Eratosthenes for finding prime numbers.

Bloom filters.

Tracking presence/absence of elements in a range.

Graph algorithms (e.g., adjacency sets for dense parts of graphs).

#### Part 4: Additional Cool Bit Manipulation Tricks

1. Isolate the Rightmost Set Bit (LSB)

Pattern: x & -x or x & (~x + 1) (since -x is ~x + 1 in two’s complement)

Java Example:

int x = 12; // Binary: 1100

int lsb = x & -x; // 1100 & (...0100) = 0100 (4)

System.out.println("Rightmost set bit of " + x + " (" + Integer.toBinary

String(x) +
") is " + lsb + " (" + Integer.toBinaryString(lsb) +

")");

Detailed Notes:

-x in two’s complement is obtained by inverting all bits of x and adding 1 ( ~x + 1 ).

This operation results in a number that has only the rightmost set bit of x turned on, and all

other bits are zero.

Example: x = 12 (0...01100) . ~x = 1...10011 . ~x + 1 = 1...10100 (-12) .

x & (-x) is 0...01100 & 1...10100 = 0...00100 (4) .

Use Case: Fenwick trees (Binary Indexed Trees), turning off the rightmost set bit.

2. Turn Off the Rightmost Set Bit

Pattern: x & (x - 1)
Java Example:

int x = 12; // Binary: 1100

int result = x & (x - 1); // 1100 & 1011 = 1000 (8)

System.out.println(Integer.toBinaryString(x) + " with rightmost set bit

off: " +
 Integer.toBinaryString(result) + " (" + result +

")");

Detailed Notes:

Subtracting 1 from x flips the rightmost set bit and all bits to its right.
ANDing x with x-1 clears the rightmost set bit.

Use Case: Brian Kernighan’s algorithm for counting set bits, checking if a number is a power

of two.

3. Get the Rightmost Clear Bit (Least Significant Clear Bit)

Pattern: ~x & (x + 1)

Java Example:

int x = 5; // Binary: ...0101

// ~x is ...1010
// x + 1 is ...0110

// ~x & (x+1) is (...1010) & (...0110) = ...0010 (2)

int lscb = ~x & (x + 1);

System.out.println("For x=" + x + " (" + Integer.toBinaryString(x) +

"), rightmost clear bit is at position represented by

" + lscb +
" (" + Integer.toBinaryString(lscb) + ")");

Detailed Notes:

x + 1 : This operation flips all trailing 1s to 0s and flips the rightmost 0 to a 1.

~x : Inverts all bits of x.

The AND operation isolates the bit corresponding to the rightmost 0 in the original x .

4. Set the Rightmost Clear Bit

Pattern: x | (x + 1)

Java Example:

int x = 5; // Binary: ...0101

// x + 1 is ...0110

// x | (x+1) is (...0101) | (...0110) = ...0111 (7)

int result = x | (x + 1);

System.out.println("For x=" + x + " (" + Integer.toBinaryString(x) +
 "), setting rightmost clear bit gives " + result +

" (" + Integer.toBinaryString(result) + ")");

Detailed Notes:

x + 1 creates a number where the rightmost 0 of x is 1, and all bits to its right are 0.

ORing this with x sets that rightmost 0 bit to 1.

5. Create a Mask with the Lowest k Bits Set

Pattern: (1 << k) - 1

Java Example:

int k = 3;

int mask = (1 << k) - 1; // (1 << 3) is 1000 (8). 8 - 1 is 0111 (7).

System.out.println("Mask with lowest " + k + " bits set: " +

Integer.toBinaryString(mask) + " (" + mask + ")");

Detailed Notes:

1 << k produces a number with only the k -th bit set (e.g., 100...0 with k zeros).

Subtracting 1 from this number sets all k lower bits to 1 (e.g., 011...1 ).

6. Check if Two Integers Have Opposite Signs

Pattern: (x ^ y) < 0

Java Example:

int x = 10, y = -5;

if ((x ^ y) < 0) {

System.out.println(x + " and " + y + " have opposite signs."); // Ou

tput
} else {

System.out.println(x + " and " + y + " have the same sign.");

int a = 10, b = 5;

if ((a ^ b) < 0) {

System.out.println(a + " and " + b + " have opposite signs.");

} else {
System.out.println(a + " and " + b + " have the same sign."); // Out
 put

Detailed Notes:

The sign bit (most significant bit) is 0 for positive numbers (and zero) and 1 for negative
numbers in two’s complement.

If x and y have opposite signs, their sign bits will be different.

The XOR operation x ^ y will result in the sign bit of the outcome being 1 if the sign bits of

x and y are different.

If the sign bit of (x ^ y) is 1, the number is negative, so (x ^ y) < 0 .

This works for all integers except if one of them is 0 (0 is usually considered non-negative, so
(positive ^ 0) is positive, (negative ^ 0) is negative). If 0 should be handled

specially, add checks.

7. Absolute Value Without Branching (for 32-bit signed int)

Pattern: (n ^ (n >> 31)) - (n >> 31)

Java Example:

int n = -10;

int mask = n >> 31; // If n is negative, mask is -1 (all 1s). If n is no

n-negative, mask is 0.

int absVal = (n ^ mask) - mask;

System.out.println("Absolute value of " + n + " is " + absVal); // Outpu

t: 10

n = 10;

mask = n >> 31; // mask is 0

absVal = (n ^ mask) - mask; // (10 ^ 0) - 0 = 10

System.out.println("Absolute value of " + n + " is " + absVal); // Outpu

t: 10

Detailed Notes:

n >> 31 : This performs a signed right shift.

If n is non-negative, its sign bit is 0. n >> 31 results in 0 .

If n is negative, its sign bit is 1. n >> 31 results in -1 (all bits set to 1).

Let mask = n >> 31 .

If n >= 0 , mask = 0 . absVal = (n ^ 0) - 0 = n .
 If n < 0 , mask = -1 . absVal = (n ^ -1) - (-1) .

n ^ -1 is equivalent to n ^ (~0) , which is ~n (bitwise NOT of n ).

So, absVal = ~n - (-1) = ~n + 1 . This is the two’s complement of n , which

is |n| .
This is a branchless way to compute absolute value, which can be faster on some architectures

where branches are expensive. Math.abs() is generally preferred for readability and is

often intrinsified by the JVM for good performance.

8. Reverse Bits of an Integer

Java Example:

int num = 10; // Example: 0...01010 for 32 bits

// Java built-in

int reversedBuiltIn = Integer.reverse(num);

System.out.println("Original: " + Integer.toBinaryString(num));

System.out.println("Reversed (built-in): " + Integer.toBinaryString(reve

rsedBuiltIn) + " (" + reversedBuiltIn + ")");

// For 10 (0...01010), reversed is 01010...0 which is 1342177280

// Manual iterative approach for 32-bit integer

int reversedManual = 0;

int n = num;

for (int j = 0; j < 32; j++) {

reversedManual <<= 1; // Make space for the next bit

if ((n & 1) == 1) { // If LSB of n is 1

reversedManual |= 1; // Set LSB of reversedManual

}

n >>= 1; // Discard LSB of n

System.out.println("Reversed (manual): " + Integer.toBinaryString(revers

edManual) + " (" + reversedManual + ")");

Detailed Notes:

Integer.reverse(int i) and Long.reverse(long l) : Reverses the order of the

bits in the two’s complement binary representation.

Integer.reverseBytes(int i) : Reverses the order of the bytes.

 The manual approach iteratively takes the LSB of the original number and appends it to the
result, building the reversed number.

9. Swap Two Specific Bits at Positions i and j (0-indexed)

Java Example:

int num = 13; // Binary: ...1101 (Bit 0 is 1, Bit 1 is 0, Bit 2 is 1, Bi

t 3 is 1)

int i = 1; // Position of first bit

int j = 2; // Position of second bit

// Get the bits at positions i and j

int bit_i = (num >> i) & 1;

int bit_j = (num >> j) & 1;

System.out.println("Original num: " + Integer.toBinaryString(num) + " ("

+ num + ")");
System.out.println("Bit at " + i + ": " + bit_i + ", Bit at " + j + ": "

+ bit_j);

int result = num;

// If the bits are different, flip them

if (bit_i != bit_j) {
// Create a mask with bits i and j set

int mask = (1 << i) | (1 << j);

result = num ^ mask; // Flip both bits

System.out.println("Num after swapping bits " + i + " and " + j + ": " +
Integer.toBinaryString(result) + " (" + result +

")");

// Example: num=13 (1101). i=1 (bit is 0), j=2 (bit is 1). They are diff

erent.

// mask = (1<<1)|(1<<2) = 0010 | 0100 = 0110

// result = 1101 ^ 0110 = 1011 (11)

Detailed Notes:
 First, extract the bits at positions i and j .

If they are different, they need to be swapped. Swapping different bits is equivalent to flipping

both of them.

Create a mask by setting the i -th and j -th bits.

XORing the original number with this mask flips both bits. If the bits were the same, this

operation would do nothing (which is correct, no swap needed).

10. Average of Two Integers Without Overflow

Pattern: (x & y) + ((x ^ y) >> 1)

Java Example:

int x = Integer.MAX_VALUE - 2;

int y = Integer.MAX_VALUE;

// (x + y) / 2 can overflow

// long sum = (long)x + y;

// int avgOverflow = (int)(sum / 2);

int avgNoOverflow = (x & y) + ((x ^ y) >> 1);

System.out.println("x = " + x + ", y = " + y);

System.out.println("Average without overflow: " + avgNoOverflow);

// Standard way for non-negative numbers or if result is expected to be

floor

// int avgStandard = x / 2 + y / 2 + (x % 2 + y % 2) / 2; // More comple

Detailed Notes:

x & y : Represents the sum of carries when x and y are added. More precisely, 2 * (x

& y) is the sum of carries.

x ^ y : Represents the sum of bits where there is no carry.

So, x + y = (x & y) << 1 + (x ^ y) .

Therefore, (x + y) / 2 = (x & y) + ((x ^ y) >> 1) .

This method avoids the intermediate sum x + y which might overflow.

The >> 1 correctly handles negative numbers if the “floor” of the average is desired in a

specific way, but for a typical arithmetic mean, this is generally robust.
11. Round to the Next Highest Power of 2

Java Example:

int n = 17; // Next power of 2 is 32

int original_n = n;

if (n <= 0) { // Handle 0 or negative inputs if needed, often result is

1 or error
n = 1;

} else {

n--; // Important step

n |= n >> 1;

n |= n >> 2;

n |= n >> 4;
n |= n >> 8;

n |= n >> 16; // For 32-bit integers. Add n |= n >> 32; for 64-bit l

ongs.

n++;

System.out.println("Next highest power of 2 for " + original_n + " is "

+ n); // 32

n = 16; // Next power of 2 is 16 (or 32 if strictly greater is needed)

// This algorithm gives 16 if n is already a power of two.

// If strictly greater is needed, check if (original_n & (origin

al_n - 1)) == 0
// and if so, multiply by 2.

original_n = n;

if (n <= 0) n = 1; else { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n

|= n >> 8; n |= n >> 16; n++; }

System.out.println("Next highest power of 2 for " + original_n + " is "

+ n); // 16

// Java 8+ has Integer.highestOneBit(n); if n is power of 2, it's n.

// If not, it's the power of 2 just less than n.

// So, for next highest:

int num = 17;

 int hob = Integer.highestOneBit(num);
int nextPowerOf2;

if (num == 0) {

nextPowerOf2 = 1;

} else if (num == hob) { // num is already a power of 2

nextPowerOf2 = num;

} else {
nextPowerOf2 = hob << 1;

System.out.println("Next highest power of 2 for " + num + " (using highe

stOneBit) is " + nextPowerOf2); // 32

Detailed Notes:

The sequence of n |= n >> k operations effectively smears the highest set bit of

(original_n - 1) to all positions to its right.

For example, if n-1 is 0001xxxx... , after these operations it becomes 00011111... .

Adding 1 ( n++ ) then results in 00100000... , which is the next power of two.

The initial n-- handles the case where n is already a power of two. If n is a power of two,

n-1 will have all bits below n 's set bit as 1s. The smearing and n++ will return n . If you
need strictly the next power of two even if n is one, you’d adjust.

Integer.highestOneBit(int i) can be used as a building block for a more concise

solution in Java 8+.

12. Binary to Gray Code

Pattern: binary ^ (binary >> 1)

Java Example:

int binaryNum = 7; // Binary: 0111

int grayCode = binaryNum ^ (binaryNum >> 1);

// 0111 ^ (0111 >> 1) = 0111 ^ 0011 = 0100 (4)

System.out.println("Binary: " + Integer.toBinaryString(binaryNum) +

" -> Gray Code: " + Integer.toBinaryString(grayCode)

" (" + grayCode + ")");

Detailed Notes: Gray codes have the property that consecutive values differ by only one bit.

13. Gray Code to Binary

 Pattern: Iterative.

Java Example:

int grayCodeNum = 4; // Gray: 0100

int binaryResult = grayCodeNum;

int mask = grayCodeNum >> 1;

while (mask != 0) {

binaryResult ^= mask;

mask >>= 1;

// Iteration 1: gray=0100. binary=0100. mask=0010. binary = 0100^0010 =

0110. mask=0001.

// Iteration 2: binary=0110. mask=0001. binary = 0110^0001 = 0111. mask=

0000.

System.out.println("Gray Code: " + Integer.toBinaryString(grayCodeNum) +

" -> Binary: " + Integer.toBinaryString(binaryResult)

+
" (" + binaryResult + ")"); // Should be 7

Detailed Notes: The most significant bit of the binary code is the same as the MSB of the Gray code.

Subsequent binary bits are determined by the previous binary bit and the current Gray code bit. The

loop effectively does this: b[i] = g[i] ^ b[i+1] .

This revised guide provides a structured approach to learning bit manipulation, focusing on practical patterns,
Java implementations, and detailed explanations to help you understand and apply these powerful techniques.

Remember that while bit tricks can be very efficient, readability and maintainability are also important; use

them judiciously. Java’s built-in methods like Integer.bitCount() or BitSet class should often be

preferred when available for clarity and optimized performance.