Bitwise Operators in C

---

Table of Contents

1. What Are Bitwise Operators?
2. Binary Number System Refresher
3. The Six Bitwise Operators
4. Bitwise AND (&)
5. Bitwise OR (|)
6. Bitwise XOR (^)
7. Bitwise NOT (~)
8. Left Shift (<<)
9. Right Shift (>>)
10. Practical Bit Manipulation Patterns
11. Common Mistakes & Traps
12. Real-World Applications
13. Frequently Asked Questions
14. Practice MCQs
15. Key Takeaways

---

1. What Are Bitwise Operators?

Bitwise operators are operators that work directly on the binary representation of integers, manipulating them bit by bit at the hardware level. Unlike arithmetic operators that work on the decimal (or numerical) value of a variable, bitwise operators examine and modify the individual bits that make up that value.

Why Learn Bitwise Operators?

• Performance: Bitwise operations are among the fastest operations a CPU can perform. They execute in a single clock cycle on most processors.
• Memory efficiency: You can pack multiple boolean flags into a single integer, saving significant memory in embedded systems and network protocols.
• Low-level programming: Essential for device drivers, embedded systems, graphics programming, cryptography, and compression algorithms.
• Algorithm optimization: Many algorithms (hashing, checksums, encryption) rely on bitwise operations.
• Understanding data: Helps you understand how data is actually stored in memory.

Key Rule

Bitwise operators only work on integer types (char, short, int, long, long long, and their unsigned variants). They do not work on float, double, or pointers.

---

2. Binary Number System Refresher

Before diving into operators, let’s ensure the binary foundation is solid.

Decimal to Binary Conversion

Decimal	Binary (8-bit)
0	0000 0000
1	0000 0001
2	0000 0010
3	0000 0011
4	0000 0100
5	0000 0101
6	0000 0110
7	0000 0111
8	0000 1000
10	0000 1010
15	0000 1111
16	0001 0000
255	1111 1111

Two’s Complement (Signed Integers)

In C, int is typically 32 bits. Negative numbers are represented using two’s complement:

1. Write the positive number in binary.
2. Invert all bits (one’s complement).
3. Add 1 to the result.

Example: Representing -5 in 32-bit two’s complement

Step 1:  5  = 0000 0000 0000 0000 0000 0000 0000 0101
Step 2: ~5  = 1111 1111 1111 1111 1111 1111 1111 1010  (one's complement)
Step 3: +1  = 1111 1111 1111 1111 1111 1111 1111 1011  (two's complement = -5)

This is why ~5 equals -6 in C — the bitwise NOT of 5 gives the one’s complement, which is one less than the two’s complement representation of -5.

Important Properties of Two’s Complement

• The most significant bit (MSB) is the sign bit: 0 = positive, 1 = negative.
• The range of a signed 32-bit integer is -2,147,483,648 to 2,147,483,647.
• There is exactly one representation of zero (unlike one’s complement).
• The negative of a number can be found by inverting all bits and adding 1.

---

3. The Six Bitwise Operators

Operator	Name	Symbol	Description
&	Bitwise AND	AND	Result bit is 1 only if both bits are 1
|	Bitwise OR	OR	Result bit is 1 if either bit is 1
^	Bitwise XOR	Exclusive OR	Result bit is 1 only if bits are different
~	Bitwise NOT	Complement	Inverts every bit (0 becomes 1, 1 becomes 0)
<<	Left Shift	Shift Left	Shifts all bits left, fills with 0 on right
>>	Right Shift	Shift Right	Shifts all bits right, fills based on type

---

4. Bitwise AND (&)

The AND operator compares each bit of two operands. The result bit is set to 1 only if both corresponding bits are 1.

Truth Table

Bit A	Bit B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example

int a = 12;   // 0000 1100
int b = 10;   // 0000 1010

int result = a & b;
printf("%d", result);   // Output: 8

Step-by-step:

  0000 1100   (12)
& 0000 1010   (10)
-----------
  0000 1000   (8)

Common Use Cases

1. Checking if a specific bit is set (Masking)

int n = 13;           // 0000 1101
int mask = 1 << 2;    // 0000 0100 (bit 2)

if (n & mask) {
    printf("Bit 2 is set!
");
} else {
    printf("Bit 2 is not set.
");
}
// Output: Bit 2 is set!

2. Checking if a number is even or odd

int n = 7;

if (n & 1) {
    printf("Odd
");
} else {
    printf("Even
");
}
// Output: Odd

The least significant bit (LSB) of an odd number is always 1. This is faster than n % 2.

3. Clearing specific bits

int flags = 0b1111;       // All flags set
int mask = ~(1 << 1);     // 1111 1101 (clear bit 1)
flags = flags & mask;     // 1111 1101

---

5. Bitwise OR (|)

The OR operator compares each bit of two operands. The result bit is set to 1 if either of the corresponding bits is 1.

Truth Table

| Bit A | Bit B | A | B | |:-----:|:-----:|:---:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

Example

int a = 12;   // 0000 1100
int b = 10;   // 0000 1010

int result = a | b;
printf("%d", result);   // Output: 14

Step-by-step:

  0000 1100   (12)
| 0000 1010   (10)
-----------
  0000 1110   (14)

Common Use Cases

1. Setting a specific bit

int flags = 0b0000;       // No flags set
flags = flags | (1 << 2); // Set bit 2
// flags is now 0b0100 (4)

2. Combining permission flags

#define READ    0b001   // 1
#define WRITE   0b010   // 2
#define EXECUTE 0b100   // 4

int permissions = READ | WRITE;  // 0b011 (3)

---

6. Bitwise XOR (^)

The XOR (Exclusive OR) operator compares each bit of two operands. The result bit is set to 1 only if the two bits are different.

Truth Table

Bit A	Bit B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Example

int a = 12;   // 0000 1100
int b = 10;   // 0000 1010

int result = a ^ b;
printf("%d", result);   // Output: 6

Step-by-step:

  0000 1100   (12)
^ 0000 1010   (10)
-----------
  0000 0110   (6)

Key Properties of XOR

1. x ^ x = 0 — Any number XORed with itself is 0.
2. x ^ 0 = x — Any number XORed with 0 remains unchanged.
3. XOR is commutative: a ^ b = b ^ a.
4. XOR is associative: a ^ (b ^ c) = (a ^ b) ^ c.
5. XOR is its own inverse: If a ^ b = c, then c ^ b = a.

Common Use Cases

1. Swapping two numbers without a temporary variable

int a = 5, b = 9;

a = a ^ b;   // a = 5 ^ 9
b = a ^ b;   // b = (5 ^ 9) ^ 9 = 5
a = a ^ b;   // a = (5 ^ 9) ^ 5 = 9

printf("a = %d, b = %d", a, b);   // a = 9, b = 5

Warning: This trick fails if a and b are the same memory location (e.g., swap(&x, &x)). In that case, a = a ^ a makes a = 0, and both end up as 0.

2. Toggling a specific bit

int flags = 0b1010;       // Bit 1 is set
flags = flags ^ (1 << 1); // Toggle bit 1 -> 0b1000
flags = flags ^ (1 << 1); // Toggle bit 1 again -> 0b1010

3. Finding the unique element

Given an array where every element appears twice except one, XOR all elements to find the unique one.

int arr[] = {4, 3, 4, 2, 3};
int unique = 0;
for (int i = 0; i < 5; i++) {
    unique ^= arr[i];
}
printf("%d", unique);   // Output: 2

4. Simple encryption/decryption

char message[] = "Hello";
char key = 0x5A;

// Encrypt
for (int i = 0; message[i]; i++) {
    message[i] ^= key;
}

// Decrypt (XOR is its own inverse)
for (int i = 0; message[i]; i++) {
    message[i] ^= key;
}

---

7. Bitwise NOT (~)

The NOT operator is a unary operator that inverts every bit of its operand — 0 becomes 1, and 1 becomes 0.

Example

unsigned int a = 5;   // 0000 0000 0000 0000 0000 0000 0000 0101
unsigned int result = ~a;

printf("%u", result);   // Output: 4294967290 (on 32-bit systems)

Step-by-step:

~ 0000 0000 0000 0000 0000 0000 0000 0101   (5)
  -----------------------------------------
  1111 1111 1111 1111 1111 1111 1111 1010   (4294967290 as unsigned)

Signed vs Unsigned Behavior

This is one of the most important distinctions:

int a = 5;
printf("%d", ~a);       // Output: -6 (two's complement)

unsigned int b = 5;
printf("%u", ~b);       // Output: 4294967290

Why does ~5 equal -6?

 5 in 32-bit:  0000 0000 0000 0000 0000 0000 0000 0101
~5:            1111 1111 1111 1111 1111 1111 1111 1010

This is the two's complement representation of -6:
- Invert back: 0000 0000 0000 0000 0000 0000 0000 0101
- Add 1:       0000 0000 0000 0000 0000 0000 0000 0110  = 6
- So original was -6

Common Use Case: Creating bit masks

// Create a mask with all bits set except bit 3
int mask = ~(1 << 3);   // 1111 1111 1111 1111 1111 1111 1111 0111

---

8. Left Shift (<<)

The left shift operator shifts all bits of a number to the left by a specified number of positions. Zeros are filled in on the right.

Syntax

value << n   // Shift value left by n positions

Example

int a = 5;    // 0000 0101
int result = a << 2;
printf("%d", result);   // Output: 20

Step-by-step:

  0000 0101   (5)
<<      2
-----------
  0001 0100   (20)

Mathematical Effect

For unsigned integers and positive signed integers (where no overflow occurs):

x << n  ==  x * 2^n

5 << 1   // 10  (5 * 2)
5 << 2   // 20  (5 * 4)
5 << 3   // 40  (5 * 8)

Important Warnings

1. Overflow on signed integers

If a left shift causes a 1 to move into the sign bit of a signed integer, the behavior is undefined.

int x = 1 << 30;    // OK on 32-bit: 1073741824
int y = 1 << 31;    // UNDEFINED BEHAVIOR! Sign bit changed

2. Shifting by the width of the type or more

int a = 5;
int b = a << 32;    // UNDEFINED BEHAVIOR! (shifting 32-bit int by 32)

The C standard says shifting by a value greater than or equal to the width of the type is undefined.

3. Shifting by a negative amount

int a = 5 << -1;    // UNDEFINED BEHAVIOR!

Common Use Cases

1. Fast multiplication by powers of 2

int x = 7;
int doubled = x << 1;       // 14
int quadrupled = x << 2;    // 28

Note: Modern compilers optimize x * 2 to x << 1 automatically. Write what is clearer, not what you think is faster.

2. Creating bit masks

int bit_k = 1 << k;         // Creates a mask with only bit k set

3. Packing data

// Pack two 16-bit values into one 32-bit integer
short high = 0x1234;
short low = 0x5678;
int packed = (high << 16) | low;   // 0x12345678

---

9. Right Shift (>>)

The right shift operator shifts all bits of a number to the right by a specified number of positions.

Syntax

value >> n   // Shift value right by n positions

Two Types of Right Shift

1. Logical Right Shift (unsigned)

For unsigned integers, zeros are always filled in on the left.

unsigned int a = 20;      // 0001 0100
unsigned int result = a >> 2;
printf("%u", result);      // Output: 5

  0001 0100   (20)
>>      2
-----------
  0000 0101   (5)

2. Arithmetic Right Shift (signed)

For signed integers, the behavior is implementation-defined in the C standard, but virtually all modern compilers perform an arithmetic right shift — the sign bit is replicated (copied) to fill the left side.

int a = -8;               // 1111 1111 1111 1111 1111 1111 1111 1000
int result = a >> 1;
printf("%d", result);     // Output: -4 (typical)

  1111 1111 1111 1111 1111 1111 1111 1000   (-8)
>>                                     1
-------------------------------------------
  1111 1111 1111 1111 1111 1111 1111 1100   (-4)

The sign bit (1 for negative) is copied, preserving the negative sign.

Mathematical Effect

For unsigned integers:

x >> n  ==  x / 2^n   (integer division, truncated toward zero)

20 >> 1   // 10  (20 / 2)
20 >> 2   // 5   (20 / 4)
20 >> 3   // 2   (20 / 8, truncated)

For positive signed integers, the same formula applies.

For negative signed integers, the result depends on the implementation, but arithmetic right shift typically gives floor(x / 2^n).

Important Warnings

Same as left shift:

• Shifting by the width of the type or more is undefined behavior.
• Shifting by a negative amount is undefined behavior.

Common Use Cases

1. Fast division by powers of 2

int x = 20;
int halved = x >> 1;        // 10
int quartered = x >> 2;     // 5

2. Extracting specific bits

int value = 0b10110110;
int nibble = (value >> 4) & 0x0F;   // Extract upper nibble: 0b1011 (11)

3. Reading a specific bit

int n = 0b1010;
int bit_2 = (n >> 2) & 1;   // 1 (bit 2 is set)

---

10. Practical Bit Manipulation Patterns

Pattern 1: Check if a number is a power of 2

A power of 2 has exactly one bit set. Subtracting 1 flips that bit and all bits after it.

int n = 16;

if (n > 0 && (n & (n - 1)) == 0) {
    printf("Power of 2
");
} else {
    printf("Not a power of 2
");
}

Why it works:

n     = 16 = 0001 0000
n - 1 = 15 = 0000 1111
n & (n-1)  = 0000 0000  -> 0, so it's a power of 2

n     = 18 = 0001 0010
n - 1 = 17 = 0001 0001
n & (n-1)  = 0001 0000  -> non-zero, not a power of 2

Pattern 2: Count set bits (Brian Kernighan’s Algorithm)

int count_set_bits(unsigned int n) {
    int count = 0;
    while (n) {
        n &= n - 1;    // Clears the lowest set bit
        count++;
    }
    return count;
}

// Example: count_set_bits(0b10110) = 3

Why it works:

For any number n, n - 1 flips all bits from the lowest set bit to the end. ANDing n with n - 1 clears that lowest set bit.

n     = 10110 (22)
n - 1 = 10101 (21)
n & (n-1) = 10100 (cleared lowest set bit)

Time Complexity: O(number of set bits), which is better than O(32) for sparse numbers.

Pattern 3: Isolate the lowest set bit

int lowest = n & (-n);

Why it works:

In two’s complement, -n is ~n + 1. This creates a number where only the lowest set bit of n is preserved.

n  = 10100 (20)
-n = 01100 (two's complement of 20)
n & (-n) = 00100 (4)

Pattern 4: Clear the lowest set bit

n = n & (n - 1);

This is the same operation used in Brian Kernighan’s algorithm.

Pattern 5: Toggle ASCII case

char c = 'A';           // 0100 0001 (65)
c = c ^ 32;             // 0110 0001 (97 = 'a')

In ASCII, uppercase and lowercase letters differ by exactly 32 (0010 0000). XORing with 32 toggles that bit.

Pattern 6: Gray Code Conversion

Gray code is a binary numeral system where two successive values differ in only one bit.

// Binary to Gray code
unsigned int binary_to_gray(unsigned int n) {
    return n ^ (n >> 1);
}

// Gray code to Binary
unsigned int gray_to_binary(unsigned int g) {
    unsigned int mask = g >> 1;
    while (mask != 0) {
        g = g ^ mask;
        mask = mask >> 1;
    }
    return g;
}

Pattern 7: Swap without temporary variable

a = a ^ b;
b = a ^ b;   // b = (a^b) ^ b = a
a = a ^ b;   // a = (a^b) ^ a = b

Warning: Fails if a and b point to the same memory location.

Pattern 8: Determine if two integers have opposite signs

int x = 10, y = -5;
if ((x ^ y) < 0) {
    printf("Opposite signs
");
}

If two numbers have opposite signs, their sign bits differ, so XORing them produces a negative number.

Pattern 9: Find the missing number

Given an array of n-1 distinct numbers in range [1, n], find the missing number.

int missing = 0;
for (int i = 1; i <= n; i++) missing ^= i;
for (int i = 0; i < n-1; i++) missing ^= arr[i];
// missing now holds the missing number

Pattern 10: Reverse bits

unsigned int reverse_bits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

---

11. Common Mistakes & Traps

Mistake 1: Confusing & with &&

int a = 4, b = 2;
printf("%d", a & b);    // 0  (bitwise AND: 0100 & 0010 = 0000)
printf("%d", a && b);   // 1  (logical AND: both non-zero, so true)

• & operates bit by bit and returns an integer.
• && is logical AND, returns 0 or 1, and short-circuits.

Mistake 2: Confusing | with ||

Same distinction as above. | is bitwise OR, || is logical OR.

Mistake 3: Assuming right shift on negative numbers is well-defined

int a = -4;
int b = a >> 1;

While most compilers give -2, the C standard says this is implementation-defined. Don’t rely on it for portable code unless you know your platform.

Mistake 4: XOR swap with same variable

int a = 5;
a = a ^ a;   // a becomes 0!
a = a ^ a;   // a stays 0
a = a ^ a;   // a stays 0

If a and b are aliases for the same variable, the XOR swap corrupts the value.

Mistake 5: Not understanding operator precedence

int result = 5 & 3 == 1;   // What does this do?

== has higher precedence than &, so this is 5 & (3 == 1) = 5 & 0 = 0.

Always use parentheses: (5 & 3) == 1.

Mistake 6: Shifting by too much

int x = 1 << 31;    // UB on 32-bit signed int
int y = 1 << 32;    // UB (shift >= width)

Mistake 7: Modifying string literals

Not directly a bitwise issue, but related to understanding memory:

char *s = "Hello";
s[0] = s[0] ^ 32;   // UNDEFINED BEHAVIOR! String literals are read-only.

---

12. Real-World Applications

1. File Permissions (Unix/Linux)

#define S_IRUSR 00400   // User read
#define S_IWUSR 00200   // User write
#define S_IXUSR 00100   // User execute

mode_t mode = S_IRUSR | S_IWUSR | S_IXUSR;  // 0b111000000 = 0700

2. Graphics: RGB Color Packing

// Pack RGB into a 32-bit integer
unsigned int color = (red << 16) | (green << 8) | blue;

// Extract components
unsigned char r = (color >> 16) & 0xFF;
unsigned char g = (color >> 8) & 0xFF;
unsigned char b = color & 0xFF;

3. Network Protocols: TCP Flags

#define SYN 0x02
#define ACK 0x10
#define FIN 0x01

if (flags & SYN) { /* Handle SYN packet */ }
if (flags & (SYN | ACK)) { /* Handle SYN-ACK packet */ }

4. Embedded Systems: GPIO Control

// Set GPIO pin 5 high
GPIO_PORT |= (1 << 5);

// Set GPIO pin 5 low
GPIO_PORT &= ~(1 << 5);

// Toggle GPIO pin 5
GPIO_PORT ^= (1 << 5);

// Read GPIO pin 5
int pin_state = (GPIO_PORT >> 5) & 1;

5. Compression: Run-Length Encoding Flags

Bitwise operations are fundamental in Huffman coding, LZ77, and other compression algorithms.

6. Cryptography

XOR is the basis of the one-time pad, stream ciphers, and many encryption algorithms.

---

13. Frequently Asked Questions

Q: What does x << n compute?

For unsigned types and positive signed types (without overflow): x multiplied by 2^n.

Q: What does x >> n compute for a positive x?

x divided by 2^n, using integer (truncating) division.

Q: How do you check if the k-th bit of a number is set?

if (n & (1 << k)) {
    printf("Bit %d is set
", k);
}

Q: How do you clear the k-th bit?

n = n & ~(1 << k);

Q: How do you set the k-th bit?

n = n | (1 << k);

Q: How do you toggle the k-th bit?

n = n ^ (1 << k);

Q: Why does ~5 equal -6 and not -5?

~5 inverts all bits of 5. In two’s complement, the bit pattern 1111...1010 represents -6, not -5. The one’s complement of 5 is -6 in two’s complement representation.

Q: Can I use bitwise operators on float or double?

No. Bitwise operators only work on integer types. To manipulate the bits of a float, you must use a union or pointer cast:

union { float f; int i; } u;
u.f = 3.14f;
printf("%x", u.i);   // View float's bit pattern

Q: Is x << 1 faster than x * 2?

On modern compilers, no. The compiler automatically optimizes x * 2 to a shift instruction. Write what is more readable (x * 2) and let the compiler optimize.

Q: What is the difference between logical and bitwise operators?

| Logical (&&, ||, !) | Bitwise (&, |, ^, ~) | |---------------------------|------------------------------| | Works on the whole value | Works on each bit individually | | Returns 0 or 1 | Returns an integer with modified bits | | Short-circuits | Does not short-circuit | | Used for boolean logic | Used for bit manipulation |

---

14. Practice MCQs

MCQ 1

int a = 6, b = 3;
printf("%d", a & b);

A. 2
B. 3
C. 6
D. 0

Answer: A (2)

  0110 (6)
& 0011 (3)
------
  0010 (2)

---

MCQ 2

int a = 6, b = 3;
printf("%d", a | b);

A. 6
B. 3
C. 7
D. 0

Answer: C (7)

  0110 (6)
| 0011 (3)
------
  0111 (7)

---

MCQ 3

int a = 5;
printf("%d", a << 1);

A. 5
B. 10
C. 2
D. 25

Answer: B (10)

5 * 2^1 = 10

---

MCQ 4

int a = 5;
printf("%d", ~a);

A. -5
B. -6
C. 5
D. 6

Answer: B (-6)

~5 inverts all bits. In 32-bit two’s complement, this is -6.

---

MCQ 5

int a = 8;
printf("%d", a >> 2);

A. 32
B. 2
C. 4
D. 16

Answer: B (2)

8 / 2^2 = 8 / 4 = 2

---

MCQ 6

int a = 5, b = 9;
printf("%d", a ^ b);

A. 12
B. 14
C. 0
D. 4

Answer: A (12)

  0101 (5)
^ 1001 (9)
------
  1100 (12)

---

MCQ 7

int n = 18;
printf("%d", (n & (n - 1)) == 0 ? 1 : 0);

A. 1
B. 0
C. -1
D. Error

Answer: B (0)

18 is not a power of 2, so n & (n-1) is non-zero.

---

MCQ 8

unsigned int a = 1;
printf("%u", ~a);

A. 0
B. 4294967294
C. -2
D. 1

Answer: B (4294967294)

With unsigned int, ~1 inverts all 32 bits, giving 1111...1110 = 4294967294.

---

MCQ 9

int x = 0b1010;
int y = x & (x - 1);
printf("%d", y);

A. 10
B. 8
C. 9
D. 0

Answer: B (8)

x = 1010 (10), x-1 = 1001 (9), x & (x-1) = 1000 (8). This clears the lowest set bit.

---

MCQ 10

int a = 5, b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf("%d %d", a, b);

A. 5 5
B. 0 0
C. 5 0
D. 0 5

Answer: B (0 0)

Since a and b are the same variable in this code (both start as 5, but the swap operates on the same memory conceptually), XOR swap fails when both operands reference the same location.

---

15. Key Takeaways

• &, |, ^, ~ operate bit by bit; << and >> shift bits left or right.
• x << n multiplies x by 2^n (for unsigned/no-overflow cases); x >> n divides positive x by 2^n.
• Right shift on negative numbers is typically sign-preserving (arithmetic shift) but is implementation-defined by the C standard.
• n & 1 checks even/odd; (n & (n - 1)) == 0 checks power of 2.
• Never confuse &/| (bitwise) with &&/|| (logical) — they behave very differently.
• XOR swap fails when both variables share the same address.
• Shifting by the width of the type or more is undefined behavior.
• Bitwise operations are foundational for systems programming, graphics, networking, and embedded development.

---

End of Notes — Continue to MCQs or Flashcards