Bitwise Operators: short notes (Programming in C)

Revision mode

Introduction

The bitwise operators work on the individual bits of integer values. They are how C programs pack flags into a word, extract fields from hardware registers and network headers, compute masks for hashing, and implement fast multiplication or division by powers of two. In GATE they appear in output-prediction questions, in "what does this function compute?" questions (counting set bits, testing for a power of two) and in traps that mix bitwise with logical operators.

Conventions: C11, LP64, 32-bit int and unsigned int, two's complement. Binary values are written with the most significant bit on the left; bit 0 is the least significant bit.

Prerequisites

Operators, Precedence and Side Effects: precedence, logical operators.
Number Systems: binary and hexadecimal.
Signed Number Representation: two's complement, for ~ and shifts of negative values.

Core concepts

The six operators

Operator	Name	Result bit is 1 when	Example on `12` (1100) and `10` (1010)
`a & b`	AND	both bits are 1	`12 & 10` is 8 (1000)
`a \| b`	inclusive OR	at least one bit is 1	`12 \| 10` is 14 (1110)
`a ^ b`	exclusive OR	the bits differ	`12 ^ 10` is 6 (0110)
`~a`	complement (NOT)	the bit of `a` is 0	`~0u` is 4294967295
`a << n`	left shift	bits move $n$ places left, zeros enter on the right	`12 << 2` is 48
`a >> n`	right shift	bits move $n$ places right	`12 >> 2` is 3

The operands must have integer type; 3.0 & 1 does not compile. Before the operation the integer promotions apply: char, short and their unsigned versions become int (when int can represent all their values). For &, | and ^ the usual arithmetic conversions then bring both operands to a common type, exactly as for + (Type Conversions). For shifts, each operand is promoted separately and the result has the type of the promoted left operand.

Bitwise versus logical

& and && are different operators.

2 & 1 is 0 (10 AND 01 share no bit) but 2 && 1 is 1 (both are nonzero).
6 | 1 is 7 but 6 || 0 is 1.
& and | always evaluate both operands and do not sequence them; && and || short-circuit.
!x is 0 or 1; ~x flips every bit. !5 is 0 while ~5 is $-6$ .

Complement and the effect of promotion

~ flips every bit of the promoted operand. With 32-bit int, ~0 is all ones, which as a signed int is $-1$ ; ~0u is 4294967295. For any int x in two's complement other than INT_MIN, ~x == -x - 1. At INT_MIN, the negation -x overflows, which is undefined behaviour (C11 6.5p5). The same identity holds for every value of an unsigned type, read modulo $2^w$ .

A common pitfall: unsigned char uc = 0; then ~uc is not 255. The value 0 is promoted to int first, and ~ gives the int $-1$ . Only when the result is stored back into an unsigned char does it become 255.

Shift rules (C11 6.5.7)

Let $w$ be the width in bits of the promoted left operand (32 for int).

If the right operand is negative or at least $w$ , the behaviour is undefined. 1 << 32 with 32-bit int is undefined, not 0.
E1 << E2: if E1 is unsigned, the result is $E1 \times 2^{E2}$ reduced modulo $2^w$ (bits shifted out are lost). If E1 is signed and nonnegative and $E1 \times 2^{E2}$ is representable, that is the result; otherwise (negative E1, or overflow) the behaviour is undefined.
E1 >> E2: if E1 is unsigned, or signed and nonnegative, the result is $\lfloor E1 / 2^{E2} \rfloor$ . If E1 is signed and negative, the result is implementation-defined. gcc on x86-64 uses an arithmetic shift (copies of the sign bit enter on the left), giving $\lfloor E1 / 2^{E2} \rfloor$ with floor toward $-\infty$ .

Consequence: on gcc, -7 >> 1 is $-4$ while -7 / 2 is $-3$ . Shifting is not division for negative signed values, because / truncates toward zero and arithmetic shift rounds toward $-\infty$ .

For nonnegative values without overflow, x << n equals $x \cdot 2^n$ and x >> n equals $\lfloor x / 2^n \rfloor$ : 5 << 3 is 40, 100 >> 3 is 12.

Precedence reminders

Shifts bind more loosely than + and -: 1 << n - 1 is 1 << (n - 1).
&, ^, | bind more loosely than == and !=: if (x & MASK == 0) tests x & (MASK == 0). Always write (x & MASK) == 0.
Among themselves: & above ^ above |.
~ is a unary operator and binds tightest of these: ~x & y is (~x) & y.

How it works: masks and single-bit operations

A mask is a value with 1s exactly in the bit positions of interest. With 1u << k as the mask for bit $k$ :

Task	Expression	Why it works
Set bit $k$	`x \| (1u << k)`	OR with 1 forces 1, OR with 0 keeps the bit
Clear bit $k$	`x & ~(1u << k)`	AND with 0 forces 0, AND with 1 keeps
Toggle bit $k$	`x ^ (1u << k)`	XOR with 1 flips, XOR with 0 keeps
Test bit $k$	`(x >> k) & 1u`	moves bit $k$ to position 0
Extract field of $m$ bits at position $p$	`(x >> p) & ((1u << m) - 1)`	shift down, keep $m$ low bits (valid for $m < w$ )

Use unsigned operands for bit manipulation. It avoids implementation-defined right shifts and undefined left shifts into the sign bit.

Worked example: single-bit operations

Let x = 0x5C, which is 0101 1100 (92).

Set bit 0: 0101 1101, which is 93.
Clear bit 2: 0101 1000, which is 88.
Toggle bit 7: 1101 1100, which is 220.
Test bit 3: (92 >> 3) & 1 is 11 & 1, which is 1.
Extract a field: with v = 0xABCD, (v >> 4) & 0xF is 0xC and (v >> 8) & 0xFF is 0xAB.

Classic bit tricks

Clearing the lowest set bit: `x & (x - 1)`

Subtracting 1 from a nonzero $x$ turns its lowest 1 into 0 and every 0 below it into 1, leaving the higher bits unchanged. ANDing with $x$ therefore clears exactly the lowest set bit. For $x = 0101\,1100$ : $x - 1 = 0101\,1011$ , and $x \,\&\, (x-1) = 0101\,1000 = 88$ .

Counting set bits (Kernighan's method)

int popcount(unsigned x) {
    int c = 0;
    while (x) {          /* loop runs once per 1 bit */
        x &= x - 1;      /* clear the lowest set bit */
        c++;
    }
    return c;
}

popcount(0x5C) is 4 and popcount(255) is 8. The loop runs exactly once per set bit, so its time is $\Theta(\text{number of 1 bits})$ . The simpler loop that tests bit 0 and shifts right runs once per bit position up to the highest 1 bit: for n = 29 (11101) it runs 5 times and counts 4.

Testing for a power of two

A positive integer is a power of two exactly when it has a single 1 bit, that is, when clearing its lowest set bit leaves 0:

int is_pow2(unsigned x) { return x && !(x & (x - 1)); }

The x && guard is necessary: for $x = 0$ , x & (x - 1) is 0 as well, but 0 is not a power of two. Results: 0 gives 0, 1 gives 1 (since $1 = 2^0$ ), 64 gives 1, 96 gives 0.

Isolating the lowest set bit: `x & -x`

For unsigned x, -x is $2^w - x$ , which in binary is ~x + 1. ANDing with x keeps only the lowest set bit: 0x5C & -0x5C is 4 (binary 100). Fenwick trees use this.

XOR properties and the XOR swap

XOR is associative and commutative, $a \oplus a = 0$ and $a \oplus 0 = a$ . Hence

p ^= q;  q ^= p;  p ^= q;   /* swaps p and q: 3, 9 becomes 9, 3 */

Two traps:

If both operands are the same object (for example through two pointers to one variable), the first step makes it 0 and it stays 0. With int r = 5; int *s = &r, *t = &r; the three steps leave r as 0.
The one-line form a ^= b ^= a ^= b; modifies a twice without sequencing: undefined behaviour in C.

XOR of all elements of an array in which every value appears twice except one leaves the unpaired value, because the pairs cancel.

Important properties and observations

Bitwise operators accept only integer operands, after the integer promotions.
~x == -x - 1 for int x other than INT_MIN (for any signed type, other than that type's minimum); ~0 is $-1$ . For unsigned operands the identity holds modulo $2^w$ .
Shift by a negative count or by at least the width is undefined.
Left shift of a negative value, or a left shift that overflows a signed type, is undefined. Right shift of a negative value is implementation-defined.
Shifts and / differ for negative operands (-7 >> 1 is $-4$ on gcc, -7 / 2 is $-3$ ).
x & (x - 1) clears the lowest set bit; x & -x keeps only it.
& and | do not short-circuit.

GATE examination perspective

"What does this function compute?" A loop of x &= x - 1 with a counter counts 1 bits; x && !(x & (x - 1)) tests for a power of two; x & 1 tests oddness.
Mixing & with && in an if condition: evaluate both meanings and see which one the code uses.
Precedence. Missing parentheses around x & m before == can change the answer. 1 << n-1 already means 1 << (n-1), not (1<<n)-1; use parentheses to show the intended expression.
Width assumptions. Results of ~ and of left shifts depend on the width of int; use the width the question gives.
Signed shifts. If a question right-shifts a negative number, it is relying on an implementation-defined result; state the arithmetic-shift assumption.

Summary

Sources

ISO/IEC 9899:2011 (C11), committee draft N1570, (consulted 2026-11-09): Section 6.3.1.1 (integer promotions), 6.5.3.3 (unary ~), 6.5.7 (bitwise shift operators), 6.5.10 to 6.5.12 (bitwise AND, exclusive OR, inclusive OR).
B. W. Kernighan and D. M. Ritchie, The C Programming Language, 2nd ed., Prentice Hall, 1988: Section 2.9 (bitwise operators).