← C

Bitwise Operations & Tricks

Embedded C & Hardware

← Bitwise Operations & Tricks

Select a question from the sidebar

18 questions in this topic

Question 1 / 18

What are the bitwise AND, OR, XOR, NOT, and shift operators in C?

C provides six bitwise operators that work on individual bits of integer values:

Operator	Symbol	Description
AND	`&`	1 only if both bits are 1
OR	`\\|`	1 if either bit is 1
XOR	`^`	1 if bits are different
NOT	`~`	Flips all bits (one's complement)
Left shift	`<<`	Shifts bits left, fills with 0
Right shift	`>>`	Shifts bits right (arithmetic or logical)

Key properties:

AND: masking (extract bits), clearing bits
OR: setting bits
XOR: toggling bits, finding differences, self-inverse (a ^ a = 0)
NOT: one's complement, ~x = -(x+1) for signed integers
Left shift by n: multiplies by 2^n
Right shift by n: divides by 2^n (for unsigned; implementation-defined for signed)

Pseudo Code

AND:  1010 & 1100 = 1000  (bits set in BOTH)
OR:   1010 | 1100 = 1110  (bits set in EITHER)
XOR:  1010 ^ 1100 = 0110  (bits that DIFFER)
NOT:  ~1010 = 0101         (flip all bits)
<<:   0011 << 2 = 1100     (multiply by 4)
>>:   1100 >> 2 = 0011     (divide by 4)

Code

#include <stdio.h>

int main(void) {
    unsigned int a = 0b1010;  /* 10 in decimal */
    unsigned int b = 0b1100;  /* 12 in decimal */

    printf("a & b  = %u\n", a & b);   /* 8  (1000) */
    printf("a | b  = %u\n", a | b);   /* 14 (1110) */
    printf("a ^ b  = %u\n", a ^ b);   /* 6  (0110) */
    printf("~a     = %u\n", ~a);      /* 4294967285 (all bits flipped) */
    printf("a << 2 = %u\n", a << 2);  /* 40 (101000) -- multiply by 4 */
    printf("b >> 2 = %u\n", b >> 2);  /* 3  (0011)   -- divide by 4 */

    /* XOR properties */
    printf("\nXOR properties:\n");
    printf("a ^ 0 = %u\n", a ^ 0);    /* a (identity) */
    printf("a ^ a = %u\n", a ^ a);    /* 0 (self-inverse) */
    printf("a ^ b ^ b = %u\n", a ^ b ^ b);  /* a (cancellation) */

    /* NOT on signed integer */
    int x = 5;
    printf("\n~5 = %d\n", ~x);  /* -6 (two's complement: ~x = -(x+1)) */

    /* Left shift = multiply by power of 2 */
    printf("3 << 4 = %d\n", 3 << 4);  /* 48 = 3 * 16 */

    /* Right shift = divide by power of 2 */
    printf("48 >> 3 = %d\n", 48 >> 3);  /* 6 = 48 / 8 */

    return 0;
}

a & b  = 8
a | b  = 14
a ^ b  = 6
~a     = 4294967285
a << 2 = 40
b >> 2 = 3

XOR properties:
a ^ 0 = 10
a ^ a = 0
a ^ b ^ b = 10

~5 = -6
3 << 4 = 48
48 >> 3 = 6

Key Points

•& (AND): both bits 1 -> 1. Used for masking and clearing bits
•| (OR): either bit 1 -> 1. Used for setting bits
•^ (XOR): different bits -> 1. Self-inverse: a ^ a = 0
•<< n: multiply by 2^n. >> n: divide by 2^n (unsigned)
•~ (NOT): flips all bits. ~x = -(x+1) for signed (two's complement)

Gotchas

•Do not confuse & (bitwise AND) with && (logical AND)
•Do not confuse | (bitwise OR) with || (logical OR)
•Right shift of signed negative integers is implementation-defined (arithmetic vs logical)
•Shifting by a negative amount or by >= bit width is undefined behavior
•Operator precedence: bitwise operators bind weaker than comparison -- use parentheses: (a & b) == 0, not a & b == 0

& AND, | OR, ^ XOR, ~ NOT, << left shift, >> right shift. AND masks, OR sets, XOR toggles. Left shift = multiply by 2^n.

•& AND, | OR, ^ XOR, ~ NOT, << left shift, >> right shift

unsigned a = 10, b = 12;
printf("%u %u %u %u %u %u\n",
    a & b,   /* 8: AND */
    a | b,   /* 14: OR */
    a ^ b,   /* 6: XOR */
    ~a,      /* NOT */
    a << 2,  /* 40: left shift */
    b >> 2); /* 3: right shift */

Don't confuse & with && or | with ||

Question 2 / 18

How do you set a specific bit in an integer?

Setting a bit means making a specific bit position 1, regardless of its current value.

Formula: num |= (1 << pos)

How it works:

(1 << pos) creates a mask with only the target bit set
|= (OR) sets that bit to 1 without affecting other bits

OR truth table: 0 | 1 = 1, 1 | 1 = 1 -- the target bit becomes 1 regardless. All other bits: x | 0 = x -- unchanged.

Bit positions are typically 0-indexed from the right (least significant bit = position 0).

Pseudo Code

SetBit(num, pos):
  mask = 1 << pos      // e.g., pos=3: 00001000
  num = num | mask     // sets bit at pos to 1
  return num

Example: num = 5 (0101), pos = 1
  mask = 0010
  0101 | 0010 = 0111 = 7

Code

#include <stdio.h>

/* Set bit at position pos (0-indexed from right) */
int setBit(int num, int pos) {
    return num | (1 << pos);
}

/* Set multiple bits using a mask */
int setBits(int num, int mask) {
    return num | mask;
}

void printBinary(unsigned int n, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

int main(void) {
    int num = 5;  /* 0101 */
    printf("Before: "); printBinary(num, 8);  /* 00000101 */

    num = setBit(num, 1);
    printf("Set bit 1: "); printBinary(num, 8);  /* 00000111 = 7 */

    num = setBit(num, 3);
    printf("Set bit 3: "); printBinary(num, 8);  /* 00001111 = 15 */

    /* Set bit that is already 1 -- no change */
    num = setBit(num, 0);
    printf("Set bit 0: "); printBinary(num, 8);  /* 00001111 = 15 */

    /* Set bits 4 and 6 at once */
    int mask = (1 << 4) | (1 << 6);  /* 01010000 */
    num = setBits(num, mask);
    printf("Set 4,6:   "); printBinary(num, 8);  /* 01011111 = 95 */

    return 0;
}

Before: 00000101
Set bit 1: 00000111
Set bit 3: 00001111
Set bit 0: 00001111
Set 4,6:   01011111

Key Points

•Set bit: num |= (1 << pos)
•OR with a mask sets target bits to 1 without changing others
•Setting an already-set bit is a no-op (idempotent)
•Bit positions are 0-indexed from the LSB (rightmost)
•Can set multiple bits at once with a combined mask

Gotchas

•1 << pos on signed int can cause undefined behavior when pos >= 31 on 32-bit systems
•Use 1U << pos (unsigned) to avoid sign issues with high bit positions
•Shifting 1 by 32 or more is undefined behavior on 32-bit int
•Forgetting that bit positions start at 0, not 1

num |= (1 << pos) -- OR with a mask that has only the target bit set. Idempotent (setting an already-set bit does nothing).

•OR with (1 << pos) sets that bit to 1

int setBit(int num, int pos) {
    return num | (1 << pos);
}
/* Example: setBit(5, 1) -> 7 (0101 | 0010 = 0111) */

Use 1U << pos for positions >= 31 to avoid signed overflow

Question 3 / 18

How do you clear a specific bit in an integer?

Clearing a bit means setting a specific bit position to 0.

Formula: num &= ~(1 << pos)

How it works:

(1 << pos) creates a mask with only the target bit set
~ inverts it: all bits are 1 except the target (which is 0)
&= (AND) clears the target bit while preserving all others

AND truth table: x & 1 = x (preserved), x & 0 = 0 (cleared).

The inverted mask has 0 only at the target position, so AND clears only that bit.

Pseudo Code

ClearBit(num, pos):
  mask = ~(1 << pos)   // e.g., pos=2: 11111011
  num = num & mask     // clears bit at pos
  return num

Example: num = 7 (0111), pos = 1
  1 << 1 = 0010
  ~0010  = 1101
  0111 & 1101 = 0101 = 5

Code

#include <stdio.h>

/* Clear bit at position pos */
int clearBit(int num, int pos) {
    return num & ~(1 << pos);
}

/* Clear all bits from MSB through pos (inclusive) */
int clearBitsFromMSB(int num, int pos) {
    int mask = (1 << pos) - 1;
    return num & mask;
}

/* Clear all bits from pos through 0 (inclusive) */
int clearBitsFromLSB(int num, int pos) {
    int mask = ~((1 << (pos + 1)) - 1);
    return num & mask;
}

void printBinary(unsigned int n, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

int main(void) {
    int num = 15;  /* 1111 */
    printf("Before: "); printBinary(num, 8);  /* 00001111 */

    printf("Clear bit 2: "); printBinary(clearBit(num, 2), 8);  /* 00001011 = 11 */
    printf("Clear bit 0: "); printBinary(clearBit(num, 0), 8);  /* 00001110 = 14 */

    /* Clear bits from MSB through bit 2 */
    int val = 0xFF;  /* 11111111 */
    printf("Clear MSB..2: "); printBinary(clearBitsFromMSB(val, 2), 8);  /* 00000011 */

    /* Clear bits from bit 2 through LSB */
    printf("Clear 2..LSB: "); printBinary(clearBitsFromLSB(val, 2), 8);  /* 11111000 */

    return 0;
}

Before: 00001111
Clear bit 2: 00001011
Clear bit 0: 00001110
Clear MSB..2: 00000011
Clear 2..LSB: 11111000

Key Points

•Clear bit: num &= ~(1 << pos)
•AND with inverted mask zeros only the target bit
•Clearing an already-clear bit is a no-op
•Can clear ranges of bits with computed masks
•(1 << pos) - 1 gives a mask of pos ones from the right

Gotchas

•Forgetting the ~ (NOT) clears everything EXCEPT the target bit (opposite of intended)
•~(1 << pos) on signed int: works in two's complement but be explicit with unsigned
•Shifting undefined behavior applies here too: 1 << 32 is UB on 32-bit int
•Clearing bit 0 of an odd number makes it even

num &= ~(1 << pos) -- AND with an inverted mask that has 0 only at the target position. Clears that bit to 0.

•AND with ~(1 << pos) to clear one bit

int clearBit(int num, int pos) {
    return num & ~(1 << pos);
}
/* clearBit(7, 1) -> 5 (0111 & 1101 = 0101) */

Forgetting ~ inverts the operation (clears all OTHER bits)

Question 4 / 18

How do you toggle a specific bit in an integer?

Toggling a bit means flipping it: 0 becomes 1 and 1 becomes 0.

Formula: num ^= (1 << pos)

How it works: XOR truth table: 0 ^ 1 = 1, 1 ^ 1 = 0. The target bit is flipped. All other bits: x ^ 0 = x -- unchanged.

Key property of XOR: It is its own inverse. Toggling twice restores the original value: (num ^ mask) ^ mask = num.

Pseudo Code

ToggleBit(num, pos):
  mask = 1 << pos
  num = num ^ mask   // flips bit at pos
  return num

Example: num = 5 (0101), pos = 2
  mask = 0100
  0101 ^ 0100 = 0001 = 1

Toggle again:
  0001 ^ 0100 = 0101 = 5 (back to original)

Code

#include <stdio.h>

int toggleBit(int num, int pos) {
    return num ^ (1 << pos);
}

void printBinary(unsigned int n, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

int main(void) {
    int num = 5;  /* 0101 */
    printf("Original: "); printBinary(num, 8);  /* 00000101 */

    int toggled = toggleBit(num, 2);
    printf("Toggle 2: "); printBinary(toggled, 8);  /* 00000001 = 1 */

    int back = toggleBit(toggled, 2);
    printf("Toggle 2: "); printBinary(back, 8);  /* 00000101 = 5 (restored) */

    /* Toggle multiple bits at once */
    int val = 0xAA;  /* 10101010 */
    int mask = 0xFF;  /* 11111111 */
    printf("\n0xAA ^ 0xFF = "); printBinary(val ^ mask, 8);  /* 01010101 = 0x55 */

    return 0;
}

Original: 00000101
Toggle 2: 00000001
Toggle 2: 00000101

0xAA ^ 0xFF = 01010101

Key Points

•Toggle bit: num ^= (1 << pos)
•XOR flips the target bit, leaves others unchanged
•XOR is self-inverse: toggle twice restores original
•Can toggle multiple bits with a multi-bit mask
•XOR with all 1s (~0 or 0xFF...) flips all bits (same as NOT)

Gotchas

•Do not confuse toggle (XOR) with set (OR) or clear (AND NOT)
•XOR is NOT the same as NOT: XOR flips selected bits, NOT flips all bits
•Same shift/UB gotchas apply: 1 << 32 is undefined for 32-bit int
•Toggle is not idempotent -- applying it twice restores the original

num ^= (1 << pos) -- XOR flips the bit at position pos. Toggle twice restores the original (XOR is self-inverse).

•XOR with (1 << pos) flips that bit

int toggleBit(int num, int pos) {
    return num ^ (1 << pos);
}
/* toggleBit(5, 2) -> 1 (0101 ^ 0100 = 0001) */

Toggle is not idempotent: applying twice gives back the original

Question 5 / 18

How do you check if a specific bit is set in an integer?

Checking a bit means testing whether a specific bit position is 1 or 0.

Formula: (num >> pos) & 1 or num & (1 << pos)

Method 1: Shift the number right by pos, then AND with 1. The result is 0 or 1.

Method 2: AND with a mask that has only the target bit set. Non-zero means the bit is set.

Method 1 is preferred in interviews because it always returns exactly 0 or 1 (not just truthy/falsy).

Pseudo Code

Method 1: (num >> pos) & 1
  Shift bit to position 0, mask with 1
  Returns exactly 0 or 1

Method 2: num & (1 << pos)
  Returns 0 or (1 << pos)
  Non-zero = bit is set

Example: num = 5 (0101), check bit 2
  Method 1: (5 >> 2) & 1 = 1 & 1 = 1
  Method 2: 5 & (1 << 2) = 0101 & 0100 = 0100 = 4 (non-zero = set)

Code

#include <stdio.h>

/* Returns 0 or 1 */
int getBit(int num, int pos) {
    return (num >> pos) & 1;
}

/* Returns 0 or non-zero (the bit's value in place) */
int isBitSet(int num, int pos) {
    return num & (1 << pos);
}

void printBinary(unsigned int n, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

int main(void) {
    int num = 42;  /* 00101010 */
    printf("num = "); printBinary(num, 8);

    for (int i = 7; i >= 0; i--)
        printf("Bit %d: %d\n", i, getBit(num, i));
    /* Bit 7: 0, Bit 6: 0, Bit 5: 1, Bit 4: 0,
       Bit 3: 1, Bit 2: 0, Bit 1: 1, Bit 0: 0 */

    /* Using isBitSet (returns non-zero, not necessarily 1) */
    printf("\nisBitSet(42, 5) = %d\n", isBitSet(42, 5));  /* 32 (non-zero = true) */
    printf("isBitSet(42, 4) = %d\n", isBitSet(42, 4));    /* 0 (false) */

    /* Practical: check if number is odd (bit 0) */
    printf("42 is %s\n", getBit(42, 0) ? "odd" : "even");  /* even */
    printf("43 is %s\n", getBit(43, 0) ? "odd" : "even");  /* odd */

    return 0;
}

num = 00101010
Bit 7: 0
Bit 6: 0
Bit 5: 1
Bit 4: 0
Bit 3: 1
Bit 2: 0
Bit 1: 1
Bit 0: 0

isBitSet(42, 5) = 32
isBitSet(42, 4) = 0
42 is even
43 is odd

Key Points

•(num >> pos) & 1 returns exactly 0 or 1
•num & (1 << pos) returns 0 or the bit value in place
•Checking bit 0 tells you if a number is odd or even
•Method 1 is preferred when you need a boolean (0/1) result
•Useful for decoding flags, permissions, and bit fields

Gotchas

•num & (1 << pos) returns 0 or 2^pos, not 0 or 1 -- do not use == 1 to check
•Right-shifting negative signed integers is implementation-defined
•Shifting by >= bit width is undefined behavior
•Do not confuse & (bitwise AND) with && (logical AND)

(num >> pos) & 1 returns 0 or 1. Alternative: num & (1 << pos) returns 0 or non-zero.

•(num >> pos) & 1 gives exactly 0 or 1

int getBit(int num, int pos) {
    return (num >> pos) & 1;
}
/* getBit(42, 5) -> 1, getBit(42, 4) -> 0 */

num & (1 << pos) returns 2^pos, not 1 -- don't compare with == 1

Question 6 / 18

How do you count the number of set bits using Brian Kernighan's algorithm?

Counting set bits (popcount / Hamming weight) is one of the most asked bit manipulation questions.

Brian Kernighan's algorithm: n = n & (n - 1) clears the lowest set bit. Repeat until n is 0. The number of iterations equals the number of set bits.

Why it works: n - 1 flips the lowest set bit and all bits below it. AND with the original clears just the lowest set bit.

Example: n = 12 (1100)

1100 & 1011 = 1000 (count=1)
1000 & 0111 = 0000 (count=2)

Time: O(k) where k = number of set bits (not O(32) like naive approach).

Alternative: Lookup table, or compiler built-in __builtin_popcount(n).

Pseudo Code

CountSetBits(n):
  count = 0
  while n != 0:
    n = n & (n - 1)  // clear lowest set bit
    count++
  return count

Naive approach:
  count = 0
  while n != 0:
    count += n & 1  // check last bit
    n >>= 1
  return count

Code

#include <stdio.h>

/* Brian Kernighan's algorithm: O(number of set bits) */
int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);  /* clear lowest set bit */
        count++;
    }
    return count;
}

/* Naive approach: O(number of total bits) */
int countSetBitsNaive(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* Lookup table approach: O(1) with precomputation */
int table[256];  /* for 8-bit chunks */

void buildTable(void) {
    table[0] = 0;
    for (int i = 1; i < 256; i++)
        table[i] = (i & 1) + table[i >> 1];
}

int countSetBitsTable(unsigned int n) {
    return table[n & 0xFF] + table[(n >> 8) & 0xFF] +
           table[(n >> 16) & 0xFF] + table[(n >> 24) & 0xFF];
}

int main(void) {
    buildTable();

    unsigned int values[] = {0, 1, 7, 15, 255, 1023, 0xFFFFFFFF};
    int n = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < n; i++) {
        printf("%10u: Kernighan=%d, Naive=%d, Table=%d\n",
               values[i],
               countSetBits(values[i]),
               countSetBitsNaive(values[i]),
               countSetBitsTable(values[i]));
    }
    /* 0: 0, 1: 1, 7: 3, 15: 4, 255: 8, 1023: 10, 4294967295: 32 */

    /* GCC/Clang built-in */
    printf("\n__builtin_popcount(255) = %d\n", __builtin_popcount(255));  /* 8 */

    return 0;
}

         0: Kernighan=0, Naive=0, Table=0
         1: Kernighan=1, Naive=1, Table=1
         7: Kernighan=3, Naive=3, Table=3
        15: Kernighan=4, Naive=4, Table=4
       255: Kernighan=8, Naive=8, Table=8
      1023: Kernighan=10, Naive=10, Table=10
4294967295: Kernighan=32, Naive=32, Table=32

__builtin_popcount(255) = 8

Key Points

•n & (n-1) clears the lowest set bit -- key insight of Kernighan's algorithm
•O(k) iterations where k = number of set bits (faster than O(32) naive)
•Lookup table gives O(1) per 8-bit chunk with precomputation
•__builtin_popcount() is the fastest on GCC/Clang (uses hardware instruction)
•Also known as Hamming weight or population count

Gotchas

•Use unsigned int to avoid issues with right-shifting negative numbers
•n & (n-1) on 0 would be -1 & 0 -- the while(n) check prevents this
•__builtin_popcount is not portable (GCC/Clang only, not MSVC)
•For 64-bit, use __builtin_popcountll or loop over all 64 bits

n & (n-1) clears the lowest set bit. Loop until n=0 and count iterations. O(k) where k = number of set bits.

•n & (n-1) clears lowest set bit, O(k) iterations

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  /* clear lowest set bit */
        count++;
    }
    return count;
}
/* countSetBits(15) -> 4, countSetBits(255) -> 8 */

Use unsigned to avoid signed right-shift issues

Question 7 / 18

How do you check if a number is a power of 2 using bitwise operations?

A power of 2 has exactly one bit set in its binary representation: 1, 2, 4, 8, 16 = 0001, 0010, 0100, 1000, 10000.

Formula: n > 0 && (n & (n - 1)) == 0

Why it works:

n & (n - 1) clears the lowest set bit
If n has exactly one bit set (power of 2), clearing it gives 0
If n has more than one bit set, clearing the lowest leaves a non-zero result

Must also check n > 0 because 0 satisfies (0 & -1) == 0 but is not a power of 2.

Alternative: n > 0 && (n & (-n)) == n -- -n isolates the lowest set bit.

Pseudo Code

IsPowerOf2(n):
  return n > 0 AND (n & (n-1)) == 0

Examples:
  8 (1000): 1000 & 0111 = 0000 -> power of 2
  6 (0110): 0110 & 0101 = 0100 -> NOT power of 2
  0: n > 0 fails -> NOT power of 2
  1 (0001): 0001 & 0000 = 0000 -> power of 2 (2^0 = 1)

Code

#include <stdio.h>

int isPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

/* Alternative using -n to isolate lowest set bit */
int isPowerOf2_v2(int n) {
    return n > 0 && (n & (-n)) == n;
}

int main(void) {
    int tests[] = {0, 1, 2, 3, 4, 5, 8, 16, 15, 32, 64, 100, 128, 256};
    int n = sizeof(tests) / sizeof(tests[0]);

    for (int i = 0; i < n; i++) {
        printf("%3d: %s\n", tests[i],
               isPowerOf2(tests[i]) ? "power of 2" : "not power of 2");
    }
    /* 0: not, 1: yes (2^0), 2: yes, 3: not, 4: yes, 5: not,
       8: yes, 16: yes, 15: not, 32: yes, 64: yes, 100: not,
       128: yes, 256: yes */

    return 0;
}

  0: not power of 2
  1: power of 2
  2: power of 2
  3: not power of 2
  4: power of 2
  5: not power of 2
  8: power of 2
 16: power of 2
 15: not power of 2
 32: power of 2
 64: power of 2
100: not power of 2
128: power of 2
256: power of 2

Key Points

•n & (n-1) == 0 means exactly one bit is set
•Must check n > 0 (zero is not a power of 2)
•1 is a power of 2 (2^0 = 1)
•O(1) time and space
•Commonly used in memory alignment checks

Gotchas

•Forgetting n > 0 check: 0 & (0-1) = 0 & 0xFFFFFFFF = 0, which passes the test
•Negative powers of 2 (-8, -16) should return false -- the n > 0 check handles this
•Do not confuse with (n & n-1): operator precedence means this is n & (n - 1), not (n & n) - 1, but adding parentheses is clearer
•This only works for integers, not floating-point

n > 0 && (n & (n-1)) == 0. Power of 2 has exactly one set bit. n & (n-1) clears it. If result is 0, it was the only bit.

•n & (n-1) clears lowest set bit; if result is 0, only one bit was set

int isPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
/* isPowerOf2(16) -> 1, isPowerOf2(15) -> 0 */

Must check n > 0: zero is not a power of 2

Question 8 / 18

How do you swap two numbers without using a temporary variable?

XOR swap uses the self-inverse property of XOR:

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

Why it works:

After step 1: a holds a ^ b
After step 2: b = (a ^ b) ^ b = a (XOR is associative and self-inverse)
After step 3: a = (a ^ b) ^ a = b

Arithmetic swap (also without temp):

a = a + b;
b = a - b;  // (a+b) - b = a
a = a - b;  // (a+b) - a = b

In practice: Just use a temporary variable. XOR swap is a trick that demonstrates XOR properties but has no practical advantage and several disadvantages.

Pseudo Code

XOR swap:
  a = a ^ b
  b = a ^ b  // now b = original a
  a = a ^ b  // now a = original b

Arithmetic swap:
  a = a + b
  b = a - b
  a = a - b

Code

#include <stdio.h>

/* XOR swap */
void xorSwap(int *a, int *b) {
    if (a == b) return;  /* CRITICAL: avoid self-swap */
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

/* Arithmetic swap */
void arithmeticSwap(int *a, int *b) {
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

/* Standard swap (use this in practice) */
void standardSwap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(void) {
    int x = 5, y = 10;
    printf("Before: x=%d, y=%d\n", x, y);

    xorSwap(&x, &y);
    printf("After XOR swap: x=%d, y=%d\n", x, y);  /* x=10, y=5 */

    arithmeticSwap(&x, &y);
    printf("After arith swap: x=%d, y=%d\n", x, y);  /* x=5, y=10 */

    /* Demonstrate the self-swap bug */
    int z = 42;
    /* xorSwap(&z, &z); would give z=0 without the guard */
    xorSwap(&z, &z);  /* safe: guard returns early */
    printf("Self-swap guarded: z=%d\n", z);  /* 42 */

    return 0;
}

Before: x=5, y=10
After XOR swap: x=10, y=5
After arith swap: x=5, y=10
Self-swap guarded: z=42

Key Points

•XOR swap: a^=b; b^=a; a^=b; -- uses XOR self-inverse property
•MUST guard against self-swap (a == b gives 0)
•Arithmetic swap risks integer overflow
•In practice, always use a temp variable -- it is clearer and often faster
•XOR swap demonstrates understanding of bit operations in interviews

Gotchas

•XOR swapping a variable with itself (same address) zeroes it: a^=a gives 0
•Arithmetic swap overflows for large integers (undefined behavior for signed)
•XOR swap is NOT faster than temp swap -- modern compilers optimize temp swap into register operations
•XOR swap does not work with floating-point directly (must use integer representation)

XOR swap: a^=b; b^=a; a^=b;. Uses XOR self-inverse property. Must guard against self-swap (same address zeroes the value). In practice, just use a temp variable.

•a^=b; b^=a; a^=b; swaps without temp

void xorSwap(int *a, int *b) {
    if (a == b) return;  /* guard! */
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Self-swap (a == b) zeroes the value -- always guard against it

Question 9 / 18

How do you find the only non-repeating element in an array where every other element appears twice?

Problem: Given an array where every element appears exactly twice except one, find the unique element.

Solution: XOR all elements together. Since a ^ a = 0 and a ^ 0 = a, all pairs cancel out, leaving only the unique element.

Why it works:

XOR is commutative and associative: order does not matter
a ^ a = 0: every pair cancels
0 ^ unique = unique: the lone element remains

Time: O(n), Space: O(1). No sorting, no hash table needed.

Variant: Two non-repeating elements -- XOR all to get a ^ b, then split into two groups based on any set bit of a ^ b (it distinguishes a from b), XOR each group separately.

Pseudo Code

FindUnique(arr, n):
  result = 0
  for each element in arr:
    result = result ^ element
  return result

Example: [2, 3, 5, 3, 2]
  0 ^ 2 = 2
  2 ^ 3 = 1
  1 ^ 5 = 4
  4 ^ 3 = 7
  7 ^ 2 = 5   (the unique element)

Code

#include <stdio.h>

/* Find the single non-repeating element: O(n) time, O(1) space */
int findUnique(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++)
        result ^= arr[i];
    return result;
}

/* Variant: find TWO non-repeating elements */
void findTwoUnique(int arr[], int n, int *x, int *y) {
    int xorAll = 0;
    for (int i = 0; i < n; i++)
        xorAll ^= arr[i];
    /* xorAll = a ^ b. Find any set bit to split into groups. */

    int diffBit = xorAll & (-xorAll);  /* isolate lowest set bit */

    *x = 0;
    *y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & diffBit)
            *x ^= arr[i];
        else
            *y ^= arr[i];
    }
}

int main(void) {
    /* Single unique element */
    int arr1[] = {2, 3, 5, 4, 5, 3, 4};
    printf("Unique: %d\n", findUnique(arr1, 7));  /* 2 */

    int arr2[] = {7, 3, 5, 3, 5};
    printf("Unique: %d\n", findUnique(arr2, 5));  /* 7 */

    /* Two unique elements */
    int arr3[] = {1, 2, 3, 2, 1, 4};
    int a, b;
    findTwoUnique(arr3, 6, &a, &b);
    printf("Two unique: %d and %d\n", a, b);  /* 3 and 4 (or 4 and 3) */

    return 0;
}

Unique: 2
Unique: 7
Two unique: 3 and 4

Key Points

•XOR all elements: pairs cancel (a^a=0), unique remains
•O(n) time, O(1) space -- no hash table needed
•XOR is commutative and associative -- order does not matter
•For two unique elements: use differing bit to split into two groups
•This is LeetCode #136 (Single Number) -- extremely common interview question

Gotchas

•Only works when all OTHER elements appear EXACTLY twice (not 3 times, etc.)
•For elements appearing 3 times, need a different approach (bit counting mod 3)
•The two-unique variant requires exactly two unique elements
•Does not work if no unique element exists (result is 0, same as a valid answer of 0)

XOR all elements: pairs cancel (a^a=0), leaving the unique one. O(n) time, O(1) space. Works because XOR is commutative, associative, and self-inverse.

•XOR all: a^a=0, 0^unique=unique

int findUnique(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++)
        result ^= arr[i];
    return result;
}
/* findUnique({2,3,5,3,2}, 5) -> 5 */

Only works when other elements appear exactly twice

Question 10 / 18

What are bit masking techniques and how are they used?

Bit masking uses bitwise operations with a mask to select, modify, or extract specific bits from a value.

Common mask operations:

Extract bits: (value >> shift) & mask -- shift desired bits to position 0, then AND with mask
Set bits: value | mask -- set specific bits to 1
Clear bits: value & ~mask -- clear specific bits to 0
Check bits: value & mask -- non-zero if any masked bits are set
Replace bits: (value & ~mask) | (new_bits & mask) -- clear then set

Mask generation:

Single bit: 1 << n
N lowest bits: (1 << n) - 1
Bit range [hi:lo]: ((1 << (hi-lo+1)) - 1) << lo

Pseudo Code

Common masks:
  Single bit at pos n:     (1 << n)
  Lowest n bits:           (1 << n) - 1
  Bits [hi:lo] inclusive:  ((1 << (hi-lo+1)) - 1) << lo

Operations:
  Extract: (value >> lo) & ((1 << width) - 1)
  Set:     value | mask
  Clear:   value & ~mask
  Replace: (value & ~mask) | (new << lo)

Code

#include <stdio.h>

/* Extract bits [hi:lo] from value */
unsigned int extractBits(unsigned int value, int hi, int lo) {
    int width = hi - lo + 1;
    unsigned int mask = (1U << width) - 1;
    return (value >> lo) & mask;
}

/* Replace bits [hi:lo] in value with new_val */
unsigned int replaceBits(unsigned int value, int hi, int lo,
                         unsigned int new_val) {
    int width = hi - lo + 1;
    unsigned int mask = ((1U << width) - 1) << lo;
    value &= ~mask;           /* clear target bits */
    value |= (new_val << lo) & mask;  /* set new bits */
    return value;
}

void printBinary(unsigned int n, int bits) {
    for (int i = bits - 1; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

/* Practical example: RGB color manipulation */
typedef unsigned int Color;

Color makeRGB(unsigned char r, unsigned char g, unsigned char b) {
    return ((Color)r << 16) | ((Color)g << 8) | (Color)b;
}

unsigned char getRed(Color c)   { return (c >> 16) & 0xFF; }
unsigned char getGreen(Color c) { return (c >> 8) & 0xFF; }
unsigned char getBlue(Color c)  { return c & 0xFF; }

int main(void) {
    unsigned int val = 0b11010110;  /* 214 */
    printf("Value: "); printBinary(val, 8);  /* 11010110 */

    /* Extract bits [5:3] */
    printf("Bits [5:3]: %u\n", extractBits(val, 5, 3));  /* 010 = 2 */

    /* Replace bits [5:3] with 7 (111) */
    unsigned int replaced = replaceBits(val, 5, 3, 7);
    printf("Replace: "); printBinary(replaced, 8);  /* 11111110 */

    /* RGB example */
    Color coral = makeRGB(255, 127, 80);
    printf("\nCoral: R=%u G=%u B=%u\n",
           getRed(coral), getGreen(coral), getBlue(coral));  /* 255 127 80 */

    return 0;
}

Value: 11010110
Bits [5:3]: 2
Replace: 11111110

Coral: R=255 G=127 B=80

Key Points

•Masking = using AND/OR/NOT with bit patterns to manipulate specific bits
•(1U << n) - 1 creates a mask of n lowest bits
•Extract: shift right, then AND with mask
•Replace: clear with AND ~mask, then set with OR
•RGB color packing is a classic real-world masking application

Gotchas

•Use 1U (unsigned) to avoid undefined behavior when shifting to the sign bit
•(1 << 32) - 1 is undefined; for all-ones mask use ~0U
•Ensure new_val does not exceed the bit width when replacing
•Mask width off-by-one: bits [5:3] has width 3, not 2

Masking: AND to extract/clear, OR to set, AND-NOT-OR to replace. Mask of n bits: (1U << n) - 1. Common in RGB, flags, registers.

•AND to extract, OR to set, AND-NOT-OR to replace

/* Extract bits [hi:lo] */
unsigned extractBits(unsigned val, int hi, int lo) {
    return (val >> lo) & ((1U << (hi - lo + 1)) - 1);
}
/* RGB: pack and unpack */
unsigned makeRGB(unsigned char r, unsigned char g, unsigned char b) {
    return (r << 16) | (g << 8) | b;
}
unsigned char getRed(unsigned c) { return (c >> 16) & 0xFF; }

Use 1U for unsigned shifts to avoid sign-bit UB

Question 11 / 18

How do you extract and insert bit fields in C?

Bit fields in C struct definitions allow you to specify the exact number of bits for each member. The compiler handles packing and extraction.

Manual extraction: Use shift and mask: (value >> offset) & ((1 << width) - 1)

Manual insertion: Clear target bits and OR in new value: (value & ~mask) | ((new_val << offset) & mask)

Struct bit fields: unsigned int field : width; -- the compiler generates the shift/mask code.

When to use struct bit fields:

Hardware register access (embedded)
Network protocol headers
File format parsing
Saving memory for flags

Pseudo Code

Struct bit field syntax:
  struct Flags {
    unsigned int read  : 1;  // 1 bit
    unsigned int write : 1;  // 1 bit
    unsigned int exec  : 1;  // 1 bit
  };

Manual extraction:
  field = (value >> offset) & ((1 << width) - 1)

Manual insertion:
  mask = ((1 << width) - 1) << offset
  value = (value & ~mask) | ((new_val << offset) & mask)

Code

#include <stdio.h>

/* Struct bit fields */
typedef struct {
    unsigned int read  : 1;
    unsigned int write : 1;
    unsigned int exec  : 1;
    unsigned int user  : 1;
    unsigned int group : 1;
} Permissions;

/* Manual bit field extraction/insertion */
unsigned int extractField(unsigned int value, int offset, int width) {
    return (value >> offset) & ((1U << width) - 1);
}

unsigned int insertField(unsigned int value, int offset, int width,
                         unsigned int field_val) {
    unsigned int mask = ((1U << width) - 1) << offset;
    value &= ~mask;                      /* clear field */
    value |= (field_val << offset) & mask;  /* insert new value */
    return value;
}

int main(void) {
    /* Struct bit fields */
    Permissions p = {0};
    p.read = 1;
    p.write = 1;
    p.exec = 0;
    p.user = 1;

    printf("Permissions: r=%u w=%u x=%u u=%u g=%u\n",
           p.read, p.write, p.exec, p.user, p.group);
    /* r=1 w=1 x=0 u=1 g=0 */

    printf("Size of Permissions: %zu bytes\n", sizeof(Permissions));
    /* Typically 4 bytes (packed into one unsigned int) */

    /* Manual bit field manipulation */
    /* Pack: [age:7][height:8][weight:8] into 23 bits */
    unsigned int packed = 0;
    packed = insertField(packed, 0, 8, 150);   /* weight at bits [7:0] */
    packed = insertField(packed, 8, 8, 175);   /* height at bits [15:8] */
    packed = insertField(packed, 16, 7, 25);   /* age at bits [22:16] */

    printf("\nPacked: 0x%X\n", packed);
    printf("Weight: %u\n", extractField(packed, 0, 8));   /* 150 */
    printf("Height: %u\n", extractField(packed, 8, 8));   /* 175 */
    printf("Age:    %u\n", extractField(packed, 16, 7));  /* 25 */

    return 0;
}

Permissions: r=1 w=1 x=0 u=1 g=0
Size of Permissions: 4 bytes

Packed: 0x19AF96
Weight: 150
Height: 175
Age:    25

Key Points

•Struct bit fields: unsigned int field : width; for compiler-managed packing
•Manual extract: (value >> offset) & ((1 << width) - 1)
•Manual insert: clear with AND ~mask, set with OR
•Bit fields save memory but have platform-dependent layout
•Used in hardware registers, network protocols, file formats

Gotchas

•Struct bit field layout (endianness, padding) is implementation-defined
•Cannot take the address of a bit field member (no &p.read)
•Bit fields wider than the base type are undefined behavior
•Mixing signed and unsigned bit fields can cause unexpected sign extension

Struct bit fields: unsigned int field : width;. Manual: extract with shift+mask, insert with clear+OR. Layout is implementation-defined.

•Struct bit fields for compiler-managed packing

typedef struct {
    unsigned int r : 1;
    unsigned int w : 1;
    unsigned int x : 1;
} Perms;

unsigned extractField(unsigned val, int off, int width) {
    return (val >> off) & ((1U << width) - 1);
}

Bit field layout is implementation-defined across platforms

Question 12 / 18

How do you reverse the bits of an integer?

Reversing bits means swapping bit 0 with bit 31, bit 1 with bit 30, and so on (for 32-bit integers).

Approach 1 -- Simple loop: Extract each bit from the right, build result from the left.

Approach 2 -- Divide and conquer: Swap adjacent bits, then adjacent 2-bit groups, then 4-bit, 8-bit, 16-bit groups. O(log n) operations.

Approach 3 -- Lookup table: Precompute reversed bytes, look up 8 bits at a time.

The simple loop is easiest to understand and most commonly expected in interviews.

Pseudo Code

Simple loop:
  result = 0
  for i = 0 to 31:
    result <<= 1            // make room
    result |= (n & 1)       // copy LSB of n to LSB of result
    n >>= 1                 // move to next bit
  return result

Divide and conquer (32-bit):
  n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)  // swap adjacent bits
  n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)  // swap 2-bit groups
  n = ((n & 0x0F0F0F0F) << 4) | ((n >> 4) & 0x0F0F0F0F)  // swap nibbles
  n = ((n & 0x00FF00FF) << 8) | ((n >> 8) & 0x00FF00FF)  // swap bytes
  n = (n << 16) | (n >> 16)                                // swap halves

Code

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

/* Simple loop: O(32) */
uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

/* Divide and conquer: O(log 32) = O(5) steps */
uint32_t reverseBitsFast(uint32_t n) {
    n = ((n & 0x55555555) << 1)  | ((n >> 1)  & 0x55555555);
    n = ((n & 0x33333333) << 2)  | ((n >> 2)  & 0x33333333);
    n = ((n & 0x0F0F0F0F) << 4)  | ((n >> 4)  & 0x0F0F0F0F);
    n = ((n & 0x00FF00FF) << 8)  | ((n >> 8)  & 0x00FF00FF);
    n = (n << 16) | (n >> 16);
    return n;
}

void printBinary32(uint32_t n) {
    for (int i = 31; i >= 0; i--)
        printf("%d", (n >> i) & 1);
    printf("\n");
}

int main(void) {
    uint32_t num = 43261596;  /* 00000010100101000001111010011100 */
    printf("Original: "); printBinary32(num);

    uint32_t rev = reverseBits(num);
    printf("Reversed: "); printBinary32(rev);
    /* 00111001011110000010100101000000 = 964176192 */
    printf("Result: %u\n", rev);  /* 964176192 */

    uint32_t rev2 = reverseBitsFast(num);
    printf("Fast:   %u\n", rev2);  /* 964176192 (same) */

    return 0;
}

Original: 00000010100101000001111010011100
Reversed: 00111001011110000010100101000000
Result: 964176192
Fast:   964176192

Key Points

•Simple loop: extract LSB, append to result, shift both
•Divide and conquer: swap at increasing group sizes (1, 2, 4, 8, 16 bits)
•Use uint32_t for guaranteed 32-bit width
•Reversing bits is different from reversing bytes (endian swap)
•This is LeetCode #190 -- common interview question

Gotchas

•Must iterate exactly 32 times (or 64 for 64-bit) -- stopping early gives wrong result
•Use unsigned types to avoid issues with right-shifting signed integers
•Bit reversal != byte reversal (endian swap)
•The divide-and-conquer constants (0x55555555 etc.) must match the bit width

Loop 32 times: extract LSB of n, append to result's LSB, shift both. Or use divide-and-conquer swaps at group sizes 1, 2, 4, 8, 16.

•Extract LSB, shift result left, OR in, shift n right

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

Must loop exactly 32 times for 32-bit -- stopping early is wrong

Question 13 / 18

How do you find the position of the rightmost set bit?

Isolating the rightmost set bit: n & (-n) gives a value with only the rightmost set bit.

Why: In two's complement, -n = ~n + 1. This flips all bits and adds 1, which means all bits below the rightmost set bit flip back, and the rightmost set bit itself stays.

Finding the position (0-indexed): Count trailing zeros. Use __builtin_ctz(n) (GCC/Clang) or a loop.

Example: n = 12 (1100)

-n = ~1100 + 1 = 0011 + 1 = 0100
n & (-n) = 1100 & 0100 = 0100 (rightmost set bit at position 2)

Pseudo Code

Isolate rightmost set bit:
  rsb = n & (-n)

Position of rightmost set bit (0-indexed):
  pos = 0
  mask = n & (-n)
  while mask > 1:
    mask >>= 1
    pos++
  return pos

Or: pos = log2(n & (-n))

Code

#include <stdio.h>

/* Isolate rightmost set bit */
int rightmostSetBit(int n) {
    return n & (-n);
}

/* Find position (0-indexed) of rightmost set bit */
int rightmostSetBitPos(int n) {
    if (n == 0) return -1;  /* no set bits */

    int pos = 0;
    int rsb = n & (-n);  /* isolate RSB */
    while (rsb > 1) {
        rsb >>= 1;
        pos++;
    }
    return pos;
}

/* Using GCC built-in */
int rightmostSetBitPosBuiltin(int n) {
    if (n == 0) return -1;
    return __builtin_ctz(n);  /* count trailing zeros */
}

int main(void) {
    int tests[] = {1, 2, 3, 4, 12, 18, 40, 0};
    int n = sizeof(tests) / sizeof(tests[0]);

    for (int i = 0; i < n; i++) {
        int val = tests[i];
        int rsb = rightmostSetBit(val);
        int pos = rightmostSetBitPos(val);
        printf("%3d: rightmost set bit value = %d, position = %d\n",
               val, rsb, pos);
    }
    /*  1: value=1, pos=0
        2: value=2, pos=1
        3: value=1, pos=0
        4: value=4, pos=2
       12: value=4, pos=2
       18: value=2, pos=1
       40: value=8, pos=3
        0: value=0, pos=-1 */

    return 0;
}

  1: rightmost set bit value = 1, position = 0
  2: rightmost set bit value = 2, position = 1
  3: rightmost set bit value = 1, position = 0
  4: rightmost set bit value = 4, position = 2
 12: rightmost set bit value = 4, position = 2
 18: rightmost set bit value = 2, position = 1
 40: rightmost set bit value = 8, position = 3
  0: rightmost set bit value = 0, position = -1

Key Points

•n & (-n) isolates the rightmost (lowest) set bit
•Position = number of trailing zeros
•__builtin_ctz() counts trailing zeros (GCC/Clang)
•Result of n & (-n) is always a power of 2
•Returns 0 when n is 0 (no set bits)

Gotchas

•__builtin_ctz(0) is undefined behavior -- always check for n == 0
•n & (-n) on unsigned: -n uses two's complement which wraps around (works correctly)
•Position is 0-indexed: rightmost bit of 1 is at position 0
•Do not confuse with leftmost set bit (MSB) which requires log2 or CLZ

n & (-n) isolates the rightmost set bit. Position = count trailing zeros. Use __builtin_ctz(n) on GCC/Clang.

•n & (-n) isolates rightmost set bit

int rightmostSetBit(int n) {
    return n & (-n);  /* isolate lowest set bit */
}
int rightmostSetBitPos(int n) {
    if (n == 0) return -1;
    return __builtin_ctz(n);  /* GCC: count trailing zeros */
}

__builtin_ctz(0) is undefined -- always check n != 0

Question 14 / 18

How does two's complement representation work and why does it matter?

Two's complement is the standard way computers represent signed integers.

How to get the negative:

Invert all bits (one's complement): ~n
Add 1: ~n + 1

So -n = ~n + 1 (equivalently, -n = ~(n - 1)).

Properties:

MSB (most significant bit) is the sign bit: 0 = positive, 1 = negative
Range for n bits: -2^(n-1) to 2^(n-1) - 1
For 32-bit int: -2,147,483,648 to 2,147,483,647
Zero has a single representation (unlike one's complement)
Arithmetic (add/subtract) works the same for signed and unsigned

Why it matters for bitwise ops:

~x = -(x + 1) (NOT equals negative minus one)
-n = ~n + 1 (negation via bit flip)
Right-shift of negative numbers is implementation-defined

Pseudo Code

Two's complement of n:
  -n = ~n + 1

Range for k-bit signed int:
  -(2^(k-1)) to (2^(k-1) - 1)

8-bit examples:
   5 = 00000101
  -5 = ~00000101 + 1 = 11111010 + 1 = 11111011

Key identity: ~x = -(x + 1)
  ~0 = -1 (all ones)
  ~5 = -6

Code

#include <stdio.h>
#include <limits.h>

void printBinary32(int n) {
    unsigned int u = (unsigned int)n;
    for (int i = 31; i >= 0; i--)
        printf("%d", (u >> i) & 1);
    printf("\n");
}

int main(void) {
    /* Two's complement representation */
    printf("  5: "); printBinary32(5);
    printf(" -5: "); printBinary32(-5);
    printf(" ~5: "); printBinary32(~5);
    printf("~5 = %d\n", ~5);     /* -6 (-(5+1)) */

    /* Verify: -n = ~n + 1 */
    int n = 42;
    printf("\n-42 == ~42 + 1: %d\n", -n == (~n + 1));  /* 1 (true) */

    /* Range of int */
    printf("\nINT_MIN:  %d\n", INT_MIN);   /* -2147483648 */
    printf("INT_MAX:  %d\n", INT_MAX);     /* 2147483647 */
    printf("-INT_MIN: "); printBinary32(INT_MIN);
    /* 10000000000000000000000000000000 */

    /* Special case: INT_MIN has no positive counterpart */
    printf("\nabs(INT_MIN) overflow: %d\n", -INT_MIN);  /* UB: typically INT_MIN */

    /* Two's complement addition */
    printf("\n5 + (-3) in binary:\n");
    printf("  5: "); printBinary32(5);
    printf(" -3: "); printBinary32(-3);
    printf("sum: "); printBinary32(5 + (-3));
    printf("= %d\n", 5 + (-3));  /* 2 */

    return 0;
}

  5: 00000000000000000000000000000101
 -5: 11111111111111111111111111111011
 ~5: 11111111111111111111111111111010
~5 = -6

-42 == ~42 + 1: 1

INT_MIN:  -2147483648
INT_MAX:  2147483647
-INT_MIN: 10000000000000000000000000000000

abs(INT_MIN) overflow: -2147483648

5 + (-3) in binary:
  5: 00000000000000000000000000000101
 -3: 11111111111111111111111111111101
sum: 00000000000000000000000000000010
= 2

Key Points

•Two's complement: -n = ~n + 1
•MSB is sign bit: 0 = positive, 1 = negative
•Range: -2^(n-1) to 2^(n-1) - 1 for n-bit signed int
•~x = -(x + 1): NOT equals negative minus one
•Addition/subtraction hardware works identically for signed and unsigned

Gotchas

•INT_MIN has no positive counterpart: -INT_MIN overflows (undefined behavior)
•abs(INT_MIN) is undefined behavior in C
•Right-shifting negative integers is implementation-defined (arithmetic vs logical)
•Before C23, signed integer overflow was undefined behavior (now two's complement is mandated)

Two's complement: -n = ~n + 1. MSB is sign bit. Range: -2^(n-1) to 2^(n-1)-1. ~x = -(x+1). Hardware add/sub works the same for signed and unsigned.

•-n = ~n + 1, ~x = -(x+1)

int n = 42;
printf("-42 = ~42 + 1: %d\n", (~n + 1) == -n);  /* 1 (true) */
printf("~5 = %d\n", ~5);  /* -6 */
printf("INT_MIN = %d, INT_MAX = %d\n", INT_MIN, INT_MAX);

-INT_MIN is undefined behavior (overflow)

Question 15 / 18

What is endianness and how does byte order affect bitwise operations?

Endianness describes the byte order in which multi-byte values are stored in memory.

Little-endian: Least significant byte first (x86, ARM default). 0x12345678 stored as 78 56 34 12.

Big-endian: Most significant byte first (network order, SPARC, some ARM). 0x12345678 stored as 12 34 56 78.

When does it matter?

Network protocols (always big-endian / "network byte order")
Reading binary files from different architectures
Accessing memory through different-sized pointers (type punning)
Serialization/deserialization

Bitwise operators work on values (not memory layout), so endianness does NOT affect &, |, ^, ~, <<, >> on variables. It ONLY matters when you look at raw memory bytes.

Pseudo Code

Little-endian: LSB at lowest address
  0x12345678 in memory: [78] [56] [34] [12]
                        addr  +1   +2   +3

Big-endian: MSB at lowest address
  0x12345678 in memory: [12] [34] [56] [78]
                        addr  +1   +2   +3

Conversion functions:
  htonl(): host to network (big-endian) long
  ntohl(): network to host long
  htons()/ntohs(): for short (16-bit)

Code

#include <stdio.h>
#include <stdint.h>
#include <arpa/inet.h>  /* htonl, ntohl */

/* Detect endianness at runtime */
int isLittleEndian(void) {
    unsigned int x = 1;
    return *((unsigned char *)&x) == 1;
}

/* Manual byte swap (endian conversion) for 32-bit */
uint32_t swapEndian32(uint32_t n) {
    return ((n >> 24) & 0x000000FF) |
           ((n >> 8)  & 0x0000FF00) |
           ((n << 8)  & 0x00FF0000) |
           ((n << 24) & 0xFF000000);
}

/* Manual byte swap for 16-bit */
uint16_t swapEndian16(uint16_t n) {
    return (n >> 8) | (n << 8);
}

int main(void) {
    printf("This system is %s-endian\n",
           isLittleEndian() ? "little" : "big");

    uint32_t val = 0x12345678;

    /* Show bytes in memory order */
    unsigned char *bytes = (unsigned char *)&val;
    printf("\n0x%X in memory: ", val);
    for (int i = 0; i < 4; i++)
        printf("%02X ", bytes[i]);
    printf("\n");  /* Little-endian: 78 56 34 12 */

    /* Byte swap */
    uint32_t swapped = swapEndian32(val);
    printf("Swapped: 0x%X\n", swapped);  /* 0x78563412 */

    /* Network byte order conversion */
    uint32_t net = htonl(val);  /* host to network */
    printf("htonl(0x12345678) = 0x%X\n", net);
    /* On little-endian: 0x78563412; on big-endian: 0x12345678 */

    uint32_t host = ntohl(net);  /* network to host */
    printf("ntohl back: 0x%X\n", host);  /* 0x12345678 */

    return 0;
}

This system is little-endian

0x12345678 in memory: 78 56 34 12 
Swapped: 0x78563412
htonl(0x12345678) = 0x78563412
ntohl back: 0x12345678
(Note: memory layout and htonl result depend on system endianness;
shown output is for little-endian systems)

Key Points

•Little-endian: LSB at lowest address (x86, most ARM)
•Big-endian: MSB at lowest address (network byte order)
•Bitwise operators work on values, not memory layout -- endianness is transparent
•Use htonl/ntohl for network byte order conversion
•Endianness matters for binary file I/O and network protocols

Gotchas

•Bitwise ops on variables are endian-agnostic; endianness only matters for raw memory access
•Type punning (casting int* to char*) exposes endianness
•Forgetting htonl/ntohl in network code causes data corruption between different-endian systems
•ARM can run in either endian mode (bi-endian) -- do not assume

Little-endian: LSB first in memory (x86). Big-endian: MSB first (network order). Bitwise ops on variables are endian-transparent. Use htonl/ntohl for network conversions.

•Endianness = byte order in memory, transparent to bitwise ops on variables

/* Detect endianness */
int isLittleEndian(void) {
    unsigned int x = 1;
    return *((unsigned char *)&x) == 1;
}
/* Byte swap */
uint32_t swapEndian32(uint32_t n) {
    return ((n>>24)&0xFF) | ((n>>8)&0xFF00) |
           ((n<<8)&0xFF0000) | ((n<<24)&0xFF000000);
}

Only matters for raw memory access, serialization, and network I/O

Question 16 / 18

How do you use bit manipulation for flags and permissions?

Bit flags use individual bits to represent boolean options, packing multiple flags into a single integer. This is extremely common in C APIs (file permissions, window styles, socket options, etc.).

Pattern: Define each flag as a power of 2. Combine flags with OR, check with AND, remove with AND-NOT.

Advantages:

Memory efficient: 32 flags in 4 bytes
Fast: single instruction for set/check/clear
Combinable: multiple flags in one parameter

Real-world examples:

Unix file permissions: rwxrwxrwx = 9 bits
open() flags: O_RDONLY | O_CREAT | O_TRUNC
fcntl() flags, select() flags, etc.

Pseudo Code

Define flags as powers of 2:
  FLAG_A = 1 << 0  = 0x01
  FLAG_B = 1 << 1  = 0x02
  FLAG_C = 1 << 2  = 0x04

Set flag:    flags |= FLAG_A
Clear flag:  flags &= ~FLAG_A
Toggle flag: flags ^= FLAG_A
Check flag:  if (flags & FLAG_A)
Combine:     flags = FLAG_A | FLAG_C

Code

#include <stdio.h>

/* Define flags as powers of 2 */
#define PERM_READ    (1 << 0)  /* 0x01 = 001 */
#define PERM_WRITE   (1 << 1)  /* 0x02 = 010 */
#define PERM_EXEC    (1 << 2)  /* 0x04 = 100 */
#define PERM_ALL     (PERM_READ | PERM_WRITE | PERM_EXEC)  /* 0x07 */

/* Using enum for type safety */
typedef enum {
    OPT_VERBOSE  = 1 << 0,
    OPT_DEBUG    = 1 << 1,
    OPT_COLOR    = 1 << 2,
    OPT_LOGFILE  = 1 << 3,
    OPT_DAEMON   = 1 << 4,
} Options;

void printPerms(int perms) {
    printf("%c%c%c",
           (perms & PERM_READ)  ? 'r' : '-',
           (perms & PERM_WRITE) ? 'w' : '-',
           (perms & PERM_EXEC)  ? 'x' : '-');
}

void processOptions(unsigned int opts) {
    if (opts & OPT_VERBOSE) printf("Verbose mode\n");
    if (opts & OPT_DEBUG)   printf("Debug mode\n");
    if (opts & OPT_COLOR)   printf("Color enabled\n");
    if (opts & OPT_LOGFILE) printf("Logging to file\n");
    if (opts & OPT_DAEMON)  printf("Running as daemon\n");
}

int main(void) {
    /* Permission flags */
    int perms = PERM_READ | PERM_WRITE;  /* rw- */
    printf("Permissions: "); printPerms(perms); printf("\n");  /* rw- */

    /* Add execute permission */
    perms |= PERM_EXEC;
    printf("After +exec: "); printPerms(perms); printf("\n");  /* rwx */

    /* Remove write permission */
    perms &= ~PERM_WRITE;
    printf("After -write: "); printPerms(perms); printf("\n");  /* r-x */

    /* Toggle execute */
    perms ^= PERM_EXEC;
    printf("Toggle exec: "); printPerms(perms); printf("\n");  /* r-- */

    /* Check specific permission */
    if (perms & PERM_READ)
        printf("Has read permission\n");

    /* Option flags */
    printf("\n");
    unsigned int opts = OPT_VERBOSE | OPT_COLOR | OPT_DAEMON;
    processOptions(opts);

    return 0;
}

Permissions: rw-
After +exec: rwx
After -write: r-x
Toggle exec: r--
Has read permission

Verbose mode
Color enabled
Running as daemon

Key Points

•Each flag is a power of 2 (only one bit set)
•Set: flags |= FLAG, Clear: flags &= ~FLAG, Check: flags & FLAG
•Combine multiple flags with OR: flags = FLAG_A | FLAG_B
•Use #define or enum for named flags
•Ubiquitous in C: Unix permissions, open() flags, socket options

Gotchas

•Flags must be powers of 2 -- using sequential values (1, 2, 3) causes overlapping bits
•if (flags & FLAG) is truthy check -- it returns the flag value, not 1
•Forgetting ~ when clearing: flags &= FLAG sets all bits EXCEPT FLAG (opposite!)
•Max 32 flags in an unsigned int (64 with unsigned long long)

Define flags as powers of 2 (1 << n). Set: |= FLAG. Clear: &= ~FLAG. Check: & FLAG. Combine: FLAG_A | FLAG_B. Ubiquitous in C APIs.

•Flags = powers of 2. Set |=, Clear &= ~, Check &

#define F_READ  (1 << 0)
#define F_WRITE (1 << 1)
#define F_EXEC  (1 << 2)

int flags = F_READ | F_WRITE;  /* set read+write */
flags |= F_EXEC;               /* add exec */
flags &= ~F_WRITE;             /* remove write */
if (flags & F_READ) { /* has read */ }

Flags must be powers of 2 or bits overlap

Question 17 / 18

How do you compute the absolute value of an integer without branching?

Computing absolute value without branching (no if statement) uses the properties of arithmetic right shift and XOR.

Formula (32-bit int):

mask = n >> 31;         // 0 if positive, -1 (all ones) if negative
abs = (n ^ mask) - mask; // or equivalently: (n + mask) ^ mask

How it works:

If n >= 0: mask = 0, so (n ^ 0) - 0 = n
If n < 0: mask = -1 (all 1s), so (n ^ -1) - (-1) = ~n + 1 = -n

n ^ -1 is the same as ~n (one's complement), and subtracting -1 is adding 1, giving two's complement negation.

Why branchless? Avoids branch misprediction penalty on modern CPUs. Useful in performance-critical inner loops.

Note: abs(INT_MIN) overflows (INT_MIN has no positive counterpart).

Pseudo Code

BranchlessAbs(n):
  mask = n >> 31        // arithmetic right shift: 0 or -1
  return (n ^ mask) - mask

Alternative:
  mask = n >> 31
  return (n + mask) ^ mask

Code

#include <stdio.h>
#include <limits.h>

/* Branchless absolute value */
int branchlessAbs(int n) {
    int mask = n >> 31;  /* 0 if positive, -1 if negative */
    return (n ^ mask) - mask;
}

/* Alternative formulation */
int branchlessAbs2(int n) {
    int mask = n >> 31;
    return (n + mask) ^ mask;
}

/* Traditional with branch */
int traditionalAbs(int n) {
    return (n < 0) ? -n : n;
}

int main(void) {
    int tests[] = {0, 5, -5, 42, -42, 100, -100, INT_MAX};
    int n = sizeof(tests) / sizeof(tests[0]);

    for (int i = 0; i < n; i++) {
        printf("abs(%d) = %d (branchless), %d (v2)\n",
               tests[i],
               branchlessAbs(tests[i]),
               branchlessAbs2(tests[i]));
    }

    /* WARNING: INT_MIN overflow */
    printf("\nabs(INT_MIN) = %d (OVERFLOW!)\n", branchlessAbs(INT_MIN));
    /* Result is still INT_MIN (undefined behavior technically) */

    return 0;
}

abs(0) = 0 (branchless), 0 (v2)
abs(5) = 5 (branchless), 5 (v2)
abs(-5) = 5 (branchless), 5 (v2)
abs(42) = 42 (branchless), 42 (v2)
abs(-42) = 42 (branchless), 42 (v2)
abs(100) = 100 (branchless), 100 (v2)
abs(-100) = 100 (branchless), 100 (v2)
abs(2147483647) = 2147483647 (branchless), 2147483647 (v2)

abs(INT_MIN) = -2147483648 (OVERFLOW!)

Key Points

•mask = n >> 31 gives 0 (positive) or -1 (negative) via arithmetic shift
•(n ^ mask) - mask: XOR with -1 is NOT, minus -1 is +1, giving two's complement negation
•Avoids branch misprediction -- useful in tight loops
•Equivalent to: (n + mask) ^ mask
•Standard abs() or ternary operator is clearer for non-performance-critical code

Gotchas

•abs(INT_MIN) overflows -- there is no positive counterpart of INT_MIN in two's complement
•n >> 31 must be arithmetic right shift (fills with sign bit) -- C guarantees this for signed ints on most implementations but it is implementation-defined before C23
•This trick assumes 32-bit int; for 64-bit, use >> 63
•Branchless code is harder to read -- comment it clearly

mask = n >> 31 gives 0 or -1. (n ^ mask) - mask gives absolute value. No branch, no if. Avoids branch misprediction.

•mask = n >> 31 (0 or -1), abs = (n ^ mask) - mask

int branchlessAbs(int n) {
    int mask = n >> 31;
    return (n ^ mask) - mask;
}

abs(INT_MIN) overflows -- no positive counterpart

Question 18 / 18

What are common interview trick questions involving bitwise operators?

Interviewers love bitwise trick questions because they test deep understanding. Here are the most common ones:

1. Check if a number is even or odd: n & 1 -- returns 0 (even) or 1 (odd). Faster than n % 2.

2. Multiply/divide by powers of 2: n << k = n * 2^k, n >> k = n / 2^k.

3. Swap two numbers: XOR swap (covered separately).

4. Turn off the rightmost set bit: n & (n - 1).

5. Isolate the rightmost set bit: n & (-n).

6. Check if power of 2: n > 0 && (n & (n-1)) == 0.

7. Compute minimum/maximum without branching:

min(a,b) = b ^ ((a ^ b) & -(a < b))
max(a,b) = a ^ ((a ^ b) & -(a < b))

8. Check if two integers have opposite signs: (a ^ b) < 0 (XOR of opposite signs has sign bit set).

9. Add 1 to an integer: ~(~n + 1) + 1 or -~n (using two's complement).

10. Convert uppercase to lowercase: ch | 0x20 (sets bit 5). Lowercase to uppercase: ch & ~0x20 (clears bit 5).

Pseudo Code

Common bitwise tricks:
  Even/odd:       n & 1
  Multiply by 2k: n << k
  Divide by 2k:   n >> k
  Clear lowest set bit: n & (n-1)
  Isolate lowest set bit: n & (-n)
  Power of 2:     n > 0 && (n & (n-1)) == 0
  Opposite signs: (a ^ b) < 0
  To lowercase:   ch | 0x20
  To uppercase:   ch & ~0x20
  Toggle case:    ch ^ 0x20

Code

#include <stdio.h>

int main(void) {
    /* 1. Even/Odd check */
    printf("7 is %s\n", (7 & 1) ? "odd" : "even");  /* odd */
    printf("8 is %s\n", (8 & 1) ? "odd" : "even");  /* even */

    /* 2. Multiply and divide by powers of 2 */
    printf("5 * 8 = %d\n", 5 << 3);    /* 40 */
    printf("40 / 4 = %d\n", 40 >> 2);  /* 10 */

    /* 3. Turn off rightmost set bit */
    printf("12 & 11 = %d\n", 12 & 11);  /* 8: 1100 & 1011 = 1000 */

    /* 4. Check opposite signs */
    int a = -5, b = 10;
    printf("%d and %d opposite signs: %s\n", a, b,
           ((a ^ b) < 0) ? "yes" : "no");  /* yes */

    /* 5. Case conversion (ASCII) */
    char upper = 'A';
    char lower = upper | 0x20;   /* 'a' */
    char back  = lower & ~0x20;  /* 'A' */
    char toggled = upper ^ 0x20; /* 'a' */
    printf("'%c' -> '%c' -> '%c', toggle: '%c'\n",
           upper, lower, back, toggled);

    /* 6. Branchless min/max */
    int x = 7, y = 3;
    int min_val = y ^ ((x ^ y) & -(x < y));
    int max_val = x ^ ((x ^ y) & -(x < y));
    printf("min(%d,%d) = %d, max = %d\n", x, y, min_val, max_val);
    /* min=3, max=7 */

    /* 7. Count leading zeros to find log2 */
    unsigned int v = 16;
    int log2 = 31 - __builtin_clz(v);
    printf("log2(%u) = %d\n", v, log2);  /* 4 */

    /* 8. Round up to next power of 2 */
    unsigned int num = 13;
    num--;
    num |= num >> 1;
    num |= num >> 2;
    num |= num >> 4;
    num |= num >> 8;
    num |= num >> 16;
    num++;
    printf("Next power of 2 after 13: %u\n", num);  /* 16 */

    /* 9. Average without overflow */
    int p = 100, q = 200;
    int avg = (p & q) + ((p ^ q) >> 1);
    printf("avg(%d, %d) = %d\n", p, q, avg);  /* 150 */

    return 0;
}

7 is odd
8 is even
5 * 8 = 40
40 / 4 = 10
12 & 11 = 8
-5 and 10 opposite signs: yes
'A' -> 'a' -> 'A', toggle: 'a'
min(7,3) = 3, max = 7
log2(16) = 4
Next power of 2 after 13: 16
avg(100, 200) = 150

Key Points

•n & 1: even/odd check (faster than n % 2)
•<< k: multiply by 2^k, >> k: divide by 2^k
•ch | 0x20: uppercase to lowercase (ASCII), ch & ~0x20: reverse
•(a ^ b) < 0: check if a and b have opposite signs
•n & (n-1): clear lowest set bit (used in popcount and power-of-2 check)

Gotchas

•Bit shift multiplication/division only works for powers of 2, not arbitrary numbers
•Case conversion trick only works for ASCII letters (A-Z, a-z), not unicode
•Branchless min/max can still cause issues on some architectures due to -(a < b) evaluation
•Overflow-safe average: (a & b) + ((a ^ b) >> 1) only works for non-negative integers as written
•Many of these tricks sacrifice readability -- use them only when performance matters or in interviews

Key tricks: n & 1 (even/odd), << k (multiply by 2^k), n & (n-1) (clear lowest bit), (a ^ b) < 0 (opposite signs), ch | 0x20 (lowercase), n & (-n) (isolate lowest bit).

•Most-asked tricks in interviews -- memorize the patterns

/* Even/odd */  int isOdd = n & 1;
/* Multiply */  int x8 = n << 3;
/* Clear LSB */ int cleared = n & (n - 1);
/* Opposite signs */ int opp = (a ^ b) < 0;
/* Lowercase */ char lo = ch | 0x20;
/* Uppercase */ char up = ch & ~0x20;
/* Next pow2 */ v--; v|=v>>1; v|=v>>2; v|=v>>4; v|=v>>8; v|=v>>16; v++;

These tricks sacrifice readability -- explain them clearly in interviews

Built by onllm.dev

Home GitHub Support awesomePrep