🔢 19. Bitwise Programming

19.1 What Is Bitwise Programming?

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

Flags and masks let a program store and change several yes/no settings in one integer. Bitwise operations are also useful when interpreting binary data and working with device interfaces.

19.2 Binary Representation — The Foundation

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

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

19.3 The Bitwise Operators

19.4 Bitwise AND &

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

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

So 12 & 10 produces 8.

19.5 AND Truth Table

19.6 Bitwise OR |

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

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

So 12 | 10 produces 14.

19.7 Bitwise XOR ^

XOR produces 1 when the two corresponding bits are different.

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

So 12 ^ 10 produces 6.

19.8 XOR Truth Table

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

The complement operator flips every bit of the promoted operand. A plain integer constant such as 5 has type int. On a two’s-complement system, flipping its bits gives the signed value -6:

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

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

19.10 Left Shift <<

A left shift moves bits toward higher positions and fills the lower positions with zeros. With unsigned arithmetic, bits that move beyond the value’s width are lost.

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

For nonnegative values, a left shift by n often corresponds to multiplying by 2^n when the result stays in range and the shift count is valid. Do not rely on this shortcut for every signed value.

19.11 Right Shift >>

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

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

Unsigned right shift fills the left with zeros. In C17, right-shifting a negative signed value is implementation-defined. Use unsigned operands for the mask operations in this lesson.

19.12 Important Shift Rules

• 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.13 Check Odd or Even Using Bitwise AND

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

number & 1

• Result 0 → even
• Result 1 → odd

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

19.14 Check Whether a Bit Is Set

To test bit position k, create a value with only that bit set. First check that k is in the range supported by the mask type:

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

Bit positions start at 0 from the least significant bit.

19.15 Set a Bit

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

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

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

19.16 Clear a Bit

Clearing a bit means forcing it to 0:

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

The one-bit mask selects the target position. Inverting it leaves a zero there and ones elsewhere. AND then clears only the selected bit.

19.17 Toggle a Bit

Toggle means 0 becomes 1 and 1 becomes 0:

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

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

19.18 Bit Mask — The Central Bitwise Technique

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

1u << 3  → 00001000

A 1 in a mask marks a position of interest. The operator determines the action: AND tests selected positions, OR sets them, XOR toggles them, and AND with the inverted mask clears them.

19.19 Count Set Bits

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

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

For a positive unsigned value, this loop visits positions up to the highest set bit. It takes O(log n) iterations as the value n grows, or at most the fixed width of its integer type.

19.20 Efficient Set-Bit Counting

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

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

Each iteration removes one set bit. If the value contains s set bits, the loop runs s times and takes O(s) time. For zero, the body does not run.

19.21 Check Whether a Number Is a Power of 2

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

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

19.22 Clear the Lowest Set Bit

The expression below removes the lowest 1-bit:

value = value & (value - 1);

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

19.23 Isolate the Lowest Set Bit

To keep only the lowest set bit:

lowest = value & (~value + 1);

For unsigned integers, the more familiar equivalent is:

lowest = value & -value;

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

19.24 Swap Two Values Using XOR

XOR can swap two integer values without a third variable:

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

19.25 Find the Unique Element Using XOR

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

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

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

19.26 Using Bits as Flags

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

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

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

19.27 Set, Clear and Toggle a Flag

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

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

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

19.28 Print a Binary Representation

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

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

This lesson’s fixed-width examples deliberately use uint32_t where available. In more general code, choose the number of value bits and validate each shift rather than assuming every unsigned int has 32 bits.

19.29 Bitwise vs Logical Operators

19.30 Common Bitwise Mistakes

• 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.31 Important Operator Precedence

Use parentheses around a bitwise result before comparing it. For example, (n & mask) != 0 tests the selected bits; n & mask != 0 is grouped differently because != has higher precedence.

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

Show the intended grouping even when you know the precedence table. This makes a mask operation easier to review and reduces accidental tests of the wrong value.

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

int main(void)
{
    uint32_t value = 0U;
    unsigned bit = 5;
    if (bit < 32)
        value |= UINT32_C(1) << bit;
    printf("Mask value: %" PRIu32 "\n", value);
    return 0;
}

Mask value: 32

19.33 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.34 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.36 Key Takeaway