Bitwise Operators
Introduction
In the world of programming, we often work with high-level abstractions like variables, functions, and objects. However, underneath it all, computers operate on bits - the fundamental 0s and 1s that represent all data in computing systems. Bitwise operators give you direct access to manipulate these individual bits, providing powerful tools for certain programming tasks.
Bitwise operations work at the binary level, directly manipulating the individual bits in a value. They're incredibly efficient and are widely used in areas like:
- Low-level device programming
- Graphics programming
- Cryptography
- Data compression
- Network protocols
- Optimization techniques
Understanding bitwise operators is essential for efficient programming in certain domains and can greatly enhance your problem-solving toolkit.
Binary Representation Refresher
Before diving into bitwise operators, let's quickly refresh how integers are stored in binary:
In most programming languages, integers are typically stored using a fixed number of bits (commonly 32 or 64 bits). For example, the decimal number 42 in binary is:
42 in decimal = 00000000 00000000 00000000 00101010 in 32-bit binary
Each bit represents a power of 2, starting from the rightmost bit (2^0 = 1) and increasing as we move left.
Common Bitwise Operators
Let's explore the main bitwise operators available in most programming languages:
1. AND (&)
The bitwise AND operator 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, it's set to 0.
Syntax:
result = a & b
Example:
let a = 12; // 1100 in binary
let b = 10; // 1010 in binary
let result = a & b; // 1000 in binary (8 in decimal)
console.log(result); // Output: 8
Visual explanation:
1 1 0 0 (12 in binary)
& 1 0 1 0 (10 in binary)
-------
1 0 0 0 (8 in binary)
Practical use: Bitwise AND is commonly used to check if a specific bit is set (has value 1) or to turn off specific bits while keeping others unchanged (masking).
2. OR (|)
The bitwise OR operator 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, it's set to 0.
Syntax:
result = a | b
Example:
let a = 12; // 1100 in binary
let b = 10; // 1010 in binary
let result = a | b; // 1110 in binary (14 in decimal)
console.log(result); // Output: 14
Visual explanation:
1 1 0 0 (12 in binary)
| 1 0 1 0 (10 in binary)
-------
1 1 1 0 (14 in binary)
Practical use: Bitwise OR is used to set specific bits to 1 while leaving other bits unchanged.
3. XOR (^)
The bitwise XOR (exclusive OR) operator compares each bit of its first operand to the corresponding bit of its second operand. If the bits are different (one is 0 and one is 1), the corresponding result bit is set to 1. Otherwise, it's set to 0.
Syntax:
result = a ^ b
Example:
let a = 12; // 1100 in binary
let b = 10; // 1010 in binary
let result = a ^ b; // 0110 in binary (6 in decimal)
console.log(result); // Output: 6
Visual explanation:
1 1 0 0 (12 in binary)
^ 1 0 1 0 (10 in binary)
-------
0 1 1 0 (6 in binary)
Practical use: XOR is widely used in cryptography, checksums, and for toggling bits. It's also used in a famous algorithm for swapping two variables without using a temporary variable.
4. NOT (~)
The bitwise NOT operator inverts all the bits of its operand. Each 0 becomes 1, and each 1 becomes 0.
Syntax:
result = ~a
Example:
let a = 12; // 00000000 00000000 00000000 00001100 in 32-bit binary
let result = ~a; // 11111111 11111111 11111111 11110011 in 32-bit binary (-13 in decimal)
console.log(result); // Output: -13
Visual explanation:
00000000 00000000 00000000 00001100 (12 in 32-bit binary)
~ ----------------------------------------
11111111 11111111 11111111 11110011 (-13 in two's complement)
Note: The result might seem surprising because most languages use two's complement representation for negative numbers. The bitwise NOT of n is equivalent to -(n+1).
Practical use: Bitwise NOT is used to create bit masks or to flip all bits in a value.
5. Left Shift (<<)
The left shift operator shifts the bits of the first operand to the left by the number of positions specified by the second operand. New bits are filled with zeros.
Syntax:
result = a << b
Example:
let a = 5; // 0101 in binary
let result = a << 2; // 10100 in binary (20 in decimal)
console.log(result); // Output: 20
Visual explanation:
0 1 0 1 (5 in binary)
<< 2 positions
1 0 1 0 0 (20 in binary)
Practical use: Left shifting is equivalent to multiplying by powers of 2. Left shifting by 1 is the same as multiplying by 2, shifting by 2 is multiplying by 4, and so on. It's commonly used for efficient multiplication.
6. Right Shift (>>)
The right shift operator shifts the bits of the first operand to the right by the number of positions specified by the second operand.
Syntax:
result = a >> b
Example:
let a = 20; // 10100 in binary
let result = a >> 2; // 00101 in binary (5 in decimal)
console.log(result); // Output: 5
Visual explanation:
1 0 1 0 0 (20 in binary)
>> 2 positions
0 0 1 0 1 (5 in binary)
Practical use: Right shifting is equivalent to integer division by powers of 2. Right shifting by 1 is the same as dividing by 2, shifting by 2 is dividing by 4, and so on.
7. Unsigned Right Shift (>>>)
Some languages (like JavaScript and Java) also provide an unsigned right shift operator, which shifts bits right but fills new bits with zeros regardless of sign.
Syntax:
result = a >>> b
Example:
let a = -5; // In 32-bit, this is a series of 1s followed by "1011"
let result = a >>> 1; // Shifts right and fills with 0, becoming a large positive number
console.log(result); // Output: 2147483645 (for a 32-bit integer)
Practical use: This operator is useful when treating a value as an unsigned number.
Common Bit Manipulation Techniques
Now that we understand the basic operators, let's look at common techniques for bit manipulation:
1. Check if a bit is set
To check if the n-th bit of a number is set (is 1):
function isBitSet(num, bit) {
return ((num & (1 << bit)) !== 0);
}
// Example usage
console.log(isBitSet(5, 0)); // Output: true (5 has bit 0 set)
console.log(isBitSet(5, 1)); // Output: false (5 has bit 1 not set)
2. Set a bit
To set (make 1) the n-th bit of a number:
function setBit(num, bit) {
return num | (1 << bit);
}
// Example usage
console.log(setBit(5, 1)); // Output: 7 (5 with bit 1 set)
3. Clear a bit
To clear (make 0) the n-th bit of a number:
function clearBit(num, bit) {
return num & ~(1 << bit);
}
// Example usage
console.log(clearBit(7, 1)); // Output: 5 (7 with bit 1 cleared)
4. Toggle a bit
To toggle (flip) the n-th bit of a number:
function toggleBit(num, bit) {
return num ^ (1 << bit);
}
// Example usage
console.log(toggleBit(5, 1)); // Output: 7 (5 with bit 1 toggled)
console.log(toggleBit(7, 1)); // Output: 5 (7 with bit 1 toggled)
5. Count set bits
To count the number of 1s in the binary representation of a number (also known as the population count or Hamming weight):
function countSetBits(num) {
let count = 0;
while (num > 0) {
count += num & 1;
num >>>= 1;
}
return count;
}
// Example usage
console.log(countSetBits(7)); // Output: 3 (7 is 111 in binary, which has three 1s)
Real-World Applications of Bitwise Operators
1. Permissions and Flags
Operating systems and programs often use individual bits to represent different permissions or flags. For example, Unix file permissions use bits to represent read, write, and execute permissions for different user categories.
// Define permission flags
const READ = 4; // 100 in binary
const WRITE = 2; // 010 in binary
const EXECUTE = 1; // 001 in binary
// Set permissions for a file (e.g., read and write, but not execute)
let filePermissions = READ | WRITE; // 110 in binary (6 in decimal)
// Check if a file has write permission
function canWrite(permissions) {
return (permissions & WRITE) !== 0;
}
console.log(canWrite(filePermissions)); // Output: true
2. Color Manipulation in Graphics Programming
RGB colors can be stored efficiently using bitwise operations, with each component (red, green, blue) taking up 8 bits.
// Create an RGB color (red=255, green=128, blue=64)
function createRGB(r, g, b) {
return (r << 16) | (g << 8) | b;
}
// Extract individual components
function getRed(color) {
return (color >> 16) & 0xFF;
}
function getGreen(color) {
return (color >> 8) & 0xFF;
}
function getBlue(color) {
return color & 0xFF;
}
let color = createRGB(255, 128, 64);
console.log(getRed(color), getGreen(color), getBlue(color)); // Output: 255 128 64
3. Efficient State Storage
When you need to keep track of multiple boolean states, using individual bits is more memory-efficient than using separate boolean variables:
// Define state flags
const IS_ACTIVE = 1; // 001 in binary
const HAS_CHILDREN = 2; // 010 in binary
const IS_MODIFIED = 4; // 100 in binary
// Initialize state
let state = 0;
// Set states
state |= IS_ACTIVE; // Make active
state |= HAS_CHILDREN; // Has children
// Check state
function isActive(state) {
return (state & IS_ACTIVE) !== 0;
}
// Toggle state
function toggleModified(state) {
return state ^ IS_MODIFIED;
}
console.log(isActive(state)); // Output: true
state = toggleModified(state);
console.log((state & IS_MODIFIED) !== 0); // Output: true
4. Fast Powers of 2 Operations
Bitwise operators provide fast ways to perform powers of 2 operations:
// Multiply by 2^n
function multiplyByPowerOf2(num, power) {
return num << power;
}
// Divide by 2^n
function divideByPowerOf2(num, power) {
return num >> power;
}
console.log(multiplyByPowerOf2(10, 3)); // Output: 80 (10 * 8)
console.log(divideByPowerOf2(80, 3)); // Output: 10 (80 / 8)
5. Checking Even/Odd Numbers
A simple application of bitwise operators is checking if a number is even or odd:
function isEven(num) {
return (num & 1) === 0;
}
function isOdd(num) {
return (num & 1) === 1;
}
console.log(isEven(42)); // Output: true
console.log(isOdd(27)); // Output: true
Performance Considerations
Bitwise operations are generally faster than their arithmetic counterparts for several reasons:
- They work directly at the hardware level
- They typically execute in a single CPU cycle
- They don't need to handle decimal points or complex number representations
However, modern compilers are smart and often optimize code. For simple operations, the performance difference might not be noticeable. Always prioritize code readability unless you're working in performance-critical sections.
Common Pitfalls and Caveats
-
Language-specific bit lengths: The exact behavior might differ across programming languages, especially regarding integer size and sign.
-
Sign extension: When shifting signed integers, be aware of sign extension which might lead to unexpected results.
-
Operator precedence: Bitwise operators often have different precedence than logical operators. Always use parentheses when combining multiple operations.
-
Logical vs. Bitwise operators: Don't confuse logical operators (
&&,||,!) with bitwise operators (&,|,~). They operate differently.
Summary
Bitwise operators provide a powerful way to manipulate data at the individual bit level. They're essential tools for low-level programming and optimization techniques. While they might seem obscure at first, understanding these operators opens up new ways to solve problems efficiently.
Key takeaways:
- Bitwise AND (
&) checks if bits are set in both operands - Bitwise OR (
|) sets bits that are set in either operand - Bitwise XOR (
^) sets bits that are set in one operand but not both - Bitwise NOT (
~) inverts all bits - Shift operators (
<<,>>,>>>) move bits left or right
As you continue your programming journey, you'll find that bitwise operators become increasingly valuable for specific problems, especially those involving performance optimization, data compression, or direct hardware interaction.
Exercises
- Write a function to check if a number is a power of 2 using bitwise operators.
- Implement a function to swap two integers without using a temporary variable (hint: use XOR).
- Write a function that returns the position of the rightmost set bit in a number.
- Create a simple "bit flags" system to track whether a student has completed different assignments.
- Implement a function to reverse the bits of an unsigned integer (e.g., 43261596 (00000010100101000001111010011100) should return 964176192 (00111001011110000010100101000000)).
Additional Resources
- Bitwise Operations in the Real World
- Bit Manipulation in Competitive Programming
- The Art of Bit Manipulation
Happy coding!
If you spot any mistakes on this website, please let me know at [email protected]. I’d greatly appreciate your feedback! :)