🔢 19. Bitwise Programming

Do not rely on memory alone when an expression becomes complicated. Parentheses make the intended operation visible to both the compiler and the reader.

if ((flags & MASK) != 0) {
    /* selected bit is set */
}

Bitwise expressions can become difficult to read when mixed with arithmetic, relational, and logical operators. Use parentheses when the intended grouping is important.

19.31 Important Operator Precedence

• Confusing bitwise and logical operators.
• Forgetting that bit positions normally start at 0.
• Using a shift count that is invalid for the operand width.
• Assuming signed right shift always behaves the same on every implementation.
• Using signed values when unsigned masks would make the intent clearer.
• Forgetting integer promotions when using small integer types such as unsigned char.
• Writing masks with the wrong type or width.
• Assuming ~x simply means “make x negative”. It flips bits; the resulting value is then interpreted as an integer.
• Using the XOR swap trick when both operands refer to the same object.

19.30 Common Bitwise Mistakes

19.29 Bitwise vs Logical Operators

For portable code, choose the width from the actual unsigned type rather than hard-coding an assumption when possible.

for (int i = width - 1; i >= 0; i--)
    printf("%u", (value >> i) & 1u);

To print an unsigned integer in binary, inspect each bit from the most significant position toward the least significant position.

19.28 Print a Binary Representation

This is one of the most practical real-world uses of bitwise programming.

flags |= READ_FLAG;      /* set */
flags &= ~READ_FLAG;     /* clear */
flags ^= READ_FLAG;      /* toggle */

if (flags & READ_FLAG)   /* test */
    printf("Enabled");

19.27 Set, Clear and Toggle a Flag

This technique can represent multiple Boolean settings compactly inside one value.

#define READ_FLAG   (1u << 0)
#define WRITE_FLAG  (1u << 1)
#define EXEC_FLAG   (1u << 2)

One integer can store several independent yes/no states. Each bit represents one flag.

19.26 Using Bits as Flags

result = 0;
for (i = 0; i < n; i++)
    result ^= a[i];

• x ^ x = 0
• x ^ 0 = x
• XOR is associative and commutative.

If every value occurs exactly twice except one value, XOR can isolate the unique value because:

19.25 Find the Unique Element Using XOR

a ^= b;
b ^= a;
a ^= b;

XOR can swap two integer values without a third variable:

19.24 Swap Two Values Using XOR

Use the technique deliberately and keep the signed/unsigned type rules in mind.

lowest = value & -value;

For unsigned integers, the more familiar equivalent is:

lowest = value & (~value + 1);

To keep only the lowest set bit:

19.23 Isolate the Lowest Set Bit

This is the same operation used by the efficient set-bit counting algorithm.

value = value & (value - 1);

The expression below removes the lowest 1-bit:

19.22 Clear the Lowest Set Bit

value != 0 && (value & (value - 1)) == 0

For a positive unsigned integer, a power of two has exactly one set bit.

19.21 Check Whether a Number Is a Power of 2

Each iteration eliminates one 1-bit, so the loop runs once per set bit rather than once per bit position.

while (value != 0) {
    value = value & (value - 1);
    count++;
}

A classic technique removes the lowest set bit in each iteration:

19.20 Efficient Set-Bit Counting

This is easy to understand and demonstrates how binary positions can be processed one at a time.

count = 0;
while (value != 0) {
    count += value & 1u;
    value >>= 1;
}

A set bit is a bit whose value is 1. The simple approach repeatedly checks the lowest bit and shifts the value:

19.19 Count Set Bits

Think of the mask as a set of switches identifying exactly which bits an operation should affect.

1u << 3  → 00001000

A mask is a carefully chosen bit pattern used to select or modify specific positions.

19.18 Bit Mask — The Central Bitwise Technique

XOR is ideal because XOR with 1 flips a bit, while XOR with 0 leaves it unchanged.

value = value ^ (1u << k);

Toggle means 0 becomes 1 and 1 becomes 0:

19.17 Toggle a Bit

The mask is first inverted so every other position remains 1 while the selected position becomes 0.

value = value & ~(1u << k);

Clearing a bit means forcing it to 0:

19.16 Clear a Bit

OR is used because a 1 in the mask turns the selected bit on.

value = value | (1u << k);

Setting a bit means forcing it to 1 without changing the other bits:

19.15 Set a Bit

Bit positions start at 0 from the least significant bit.

mask = 1u << k;
if (value & mask)
    /* bit k is set */

To test bit position k, build a mask with only that bit set:

19.14 Check Whether a Bit Is Set

10 = 1010   → 10 & 1 = 0
11 = 1011   → 11 & 1 = 1

• Result 0 → even
• Result 1 → odd

number & 1

The least significant bit tells whether a nonnegative integer is odd or even.

19.13 Check Odd or Even Using Bitwise AND

• The right operand must be nonnegative.
• Its value must be less than the width in bits of the promoted left operand.
• Do not assume signed shifts behave like mathematical multiplication or division for every value.
• Use unsigned integers when implementing masks and bit fields that require predictable binary behavior.

19.12 Important Shift Rules

For unsigned values, zero bits are shifted in from the left. For negative signed values, the result of right shift is implementation-defined, so use unsigned types when you need predictable bit manipulation.

20      = 00010100
20 >> 1 = 00001010 = 10
20 >> 2 = 00000101 = 5

A right shift moves bits toward lower positions. Bits shifted out on the right are discarded.

19.11 Right Shift >>

For nonnegative values, a left shift by n often corresponds to multiplying by 2^n, but shift expressions must still respect C's type and undefined-behavior rules.

5       = 00000101
5 << 1  = 00001010 = 10
5 << 2  = 00010100 = 20

A left shift moves bits toward higher positions and inserts zeros into the vacated low-order positions.

19.10 Left Shift <<

The resulting bit pattern represents -6 in two’s complement.

 5  = 00000000 00000000 00000000 00000101
~5  = 11111111 11111111 11111111 11111010

NOT flips every bit. For a signed C integer, the result must also be interpreted using the representation of signed integers on the implementation. On the usual two’s-complement representation:

19.9 Bitwise NOT ~ — Why Does ~5 Become -6?

19.8 XOR Truth Table

So 12 ^ 10 produces 6.

12 = 1100
10 = 1010
     ----
^    0110 = 6

XOR produces 1 when the two corresponding bits are different.

19.7 Bitwise XOR ^

So 12 | 10 produces 14.

12 = 1100
10 = 1010
     ----
|    1110 = 14

OR produces 1 when at least one corresponding bit is 1.

19.6 Bitwise OR |

19.5 AND Truth Table

So 12 & 10 produces 8.

12 = 1100
10 = 1010
     ----
&    1000 = 8

AND examines corresponding bits and produces 1 only when both input bits are 1.

19.4 Bitwise AND &

19.3 The Bitwise Operators

For example, 10 is 00001010 because 8 + 2 = 10.

For an 8-bit unsigned value, each position represents a power of 2:

19.2 Binary Representation — The Foundation

Bitwise operations are especially useful when a program needs compact flags, masks, device control, binary protocols, permissions, or low-level data manipulation.

Bitwise programming works directly with the individual bits of an integer. Each bit is either 0 or 1.

19.1 What Is Bitwise Programming?

19.32 Quick Revision

INTERACTIVE LEARNING

🎬 Bitwise Programming — Bit Mask Flow

Follow how a mask is created, used to check a selected bit, and then used to set that bit.

▶ Open Visualization

—

19.33 Quick MCQs

Select an answer first, then click Check Answer. A correct choice becomes green. If the answer is wrong, your choice becomes red and the correct option becomes green. The explanation appears below.

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int a, b;

    scanf("%u %u", &a, &b);
    printf("%u", a & b);

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int a, b;

    scanf("%u %u", &a, &b);
    printf("%u", a | b);

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int a, b;

    scanf("%u %u", &a, &b);
    printf("%u", a ^ b);

    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;

    scanf("%" SCNu32, &n);
    printf("%" PRIu32, (uint32_t)~n);

    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;

    scanf("%" SCNu32, &n);
    printf("%" PRIu32, (uint32_t)(n << 1));

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int n;

    scanf("%u", &n);
    printf("%u", n >> 2);

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    int n;

    scanf("%d", &n);
    printf("%s", ((unsigned int)n & 1u) ? "Odd" : "Even");

    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int k;

    scanf("%" SCNu32 " %u", &n, &k);

    uint32_t mask = UINT32_C(1) << k;
    printf("%s", (n & mask) ? "Set" : "Not Set");

    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int k;

    scanf("%" SCNu32 " %u", &n, &k);
    n |= UINT32_C(1) << k;

    printf("%" PRIu32, n);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int k;

    scanf("%" SCNu32 " %u", &n, &k);
    n &= ~(UINT32_C(1) << k);

    printf("%" PRIu32, n);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int k;

    scanf("%" SCNu32 " %u", &n, &k);
    n ^= UINT32_C(1) << k;

    printf("%" PRIu32, n);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int count = 0;

    scanf("%" SCNu32, &n);

    while (n != 0)
    {
        count += n & 1u;
        n >>= 1;
    }

    printf("%u", count);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int count = 0;

    scanf("%" SCNu32, &n);

    while (n != 0)
    {
        n &= n - 1;
        count++;
    }

    printf("%u", count);
    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int n;

    scanf("%u", &n);

    printf("%s",
           (n != 0u && (n & (n - 1u)) == 0u)
               ? "Power of 2"
               : "Not Power of 2");

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    int n;
    int result = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int value;
        scanf("%d", &value);
        result ^= value;
    }

    printf("%d", result);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;

    scanf("%" SCNu32, &n);

    for (int i = 31; i >= 0; i--)
        putchar((n & (UINT32_C(1) << i)) ? '1' : '0');

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    unsigned int a, b;

    scanf("%u %u", &a, &b);

    a ^= b;
    b ^= a;
    a ^= b;

    printf("%u %u", a, b);
    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main()
{
    uint32_t n;
    unsigned int k;

    scanf("%" SCNu32 " %u", &n, &k);

    uint32_t mask = UINT32_C(1) << k;

    printf("Set = %" PRIu32 "\n", n | mask);
    printf("Clear = %" PRIu32 "\n", n & ~mask);
    printf("Toggle = %" PRIu32, n ^ mask);

    return 0;
}

Run your program to see the output.

#include <stdio.h>

int main()
{
    const unsigned int READ = 1u << 0;
    const unsigned int WRITE = 1u << 1;
    const unsigned int EXECUTE = 1u << 2;

    unsigned int permissions = 0u;
    int readFlag, writeFlag, executeFlag;

    scanf("%d %d %d", &readFlag, &writeFlag, &executeFlag);

    if (readFlag) permissions |= READ;
    if (writeFlag) permissions |= WRITE;
    if (executeFlag) permissions |= EXECUTE;

    printf("READ=%s WRITE=%s EXECUTE=%s",
           (permissions & READ) ? "Yes" : "No",
           (permissions & WRITE) ? "Yes" : "No",
           (permissions & EXECUTE) ? "Yes" : "No");

    return 0;
}

Run your program to see the output.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;

    scanf("%d", &n);

    unsigned int *a = malloc((size_t)n * sizeof *a);

    if (a == NULL)
        return 1;

    unsigned int x = 0u;

    for (int i = 0; i < n; i++)
    {
        scanf("%u", &a[i]);
        x ^= a[i];
    }

    unsigned int mask = x & (~x + 1u);
    unsigned int first = 0u;
    unsigned int second = 0u;

    for (int i = 0; i < n; i++)
    {
        if (a[i] & mask)
            first ^= a[i];
        else
            second ^= a[i];
    }

    if (first > second)
    {
        unsigned int temp = first;
        first = second;
        second = temp;
    }

    printf("%u %u", first, second);

    free(a);
    return 0;
}

19.35 Key Takeaway