Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

Preface

Suddenly realized that bitwise operations are quite useful, so I’m writing this article to share some insights…

Note: I’ve included all the bitwise operation concepts I could think of, so this article is quite lengthy, please bear with me! If any part is unclear or insufficiently detailed, feel free to supplement in the comments section. Thanks for your support!

Reference code in this article is written in C++.

Without further ado, let’s get started.

Basic Operations

Those with prior knowledge can skip this section.

Brief rules of bitwise operations:

Detailed explanations:

Bitwise NOT

Bitwise NOT (~x) is the simplest unary operation. Simply flip each bit of the operand. Examples:
~0011 = 1100
~1011 = 0100
Property: ~(~x) = x

Bitwise AND

Bitwise AND (x & y) takes two operands. For each corresponding bit pair:

Examples:
0011 & 1100 = 0000
1010 & 1011 = 1010

Properties:

• Commutative: a & b = b & a
• Associative: a & b & c = a & (b & c)
• Idempotent: a & a = a
• AND with 0: 0 & a1 & a2 & ... = 0
• AND with all-1s: a & inf = a

Bitwise OR

Bitwise OR (x | y) takes two operands. For each corresponding bit pair:

Examples:
1100 | 0011 = 1111
1010 | 0001 = 1011

Properties:

• Commutative: a | b = b | a
• Associative: a | b | c = a | (b | c)
• Idempotent: a | a = a
• OR with 0: a | 0 = a
• OR with all-1s: a | inf = inf

XOR

XOR (x ^ y or $x\oplus y$) takes two operands. For each corresponding bit pair:

Examples:
1000 ^ 1011 = 0011
0101 ^ 1010 = 1111

Properties:

• Commutative: $a\oplus b=b\oplus a$
• Associative: $a\oplus b\oplus c=a\oplus(b\oplus c)$
• Self-inverse: $a\oplus a=0$
• XOR with 0: $a\oplus 0=a$
• Multiple XOR: $a\oplus b\oplus b=a\oplus 0=a$
• XOR with all-1s: $a\oplus \infty=~a$
• If $a\oplus b=c$, then $a\oplus c=b$.

Shifts

Shifts include left shift (<<) and right shift (>>).

• a << b: Append b zeros to the right of a’s binary.
• a >> b: Remove b bits from the right of a’s binary.

Properties:

• (a << b) >> b = a (when no overflow)
• a << b ≈ $a\times 2^b$
• a >> b ≈ $\lfloor\frac{a}{2^b}\rfloor$

Exercises

Determine Power of Two

Problem: Given integer N, check if it’s a power of two.

Luogu P1100 High-Low Swap

Problem: Given 32-bit integer x, swap its high 16 bits and low 16 bits.

Solution: ans = (x >> 16) | (x << 16) Explanation:

Note: Use 32-bit unsigned integer to allow natural overflow when shifting.

Reference code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
    unsigned int x;
    scanf("%u", &x);
    printf("%u\n", (x >> 16) | (x << 16));
    return 0;
}

Find Unique Number

Given sequence A=(A₁,A₂,…,A₂ₙ₊₁) where N numbers appear twice and one appears once. Find the unique number.

- O(N) time, O(N) space solution
Count occurrences and find the singleton.

- O(N) time, O(1) space solution
Compute XOR sum S = A₁^A₂^…^A₂ₙ₊₁. All duplicates cancel out, leaving the unique number.

Reference code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    n = (n << 1) + 1;
    int ans = 0;
    while(n--)
    {
        int x;
        scanf("%d", &x);
        ans ^= x;
    }
    printf("%d\n", ans);
    return 0;
}

AtCoder ABC 261 E - Many Operations

Solution: For each i=1..N, track how each bit of 0/1 transforms after first i operations using prefix-like approach. Time complexity O(N).

Reference code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// https://atcoder.jp/contests/abc261/submissions/33495431
#include <cstdio>
using namespace std;

int main()
{
    unsigned n, c, zero = 0, one = 0xffffffff;
    scanf("%d%d", &n, &c);
    while(n--)
    {
        int t, a;
        scanf("%d%d", &t, &a);
        if(t == 1) one &= a, zero &= a;
        else if(t == 2) one |= a, zero |= a;
        else one ^= a, zero ^= a;
        printf("%d\n", c = (c & one) | (~c & zero));
    }
    return 0;
}

Extended Concepts & Operations

lowbit

lowbit(x) returns the least significant 1-bit, e.g., lowbit(10010) = 10, lowbit(1) = 1. Used in Fenwick Trees.

Calculating lowbit

1. Brute force:

   1 2 3 4 5 6 7

   int lowbit(int x) { int res = 1; while(x && !(x & 1)) x >>= 1, res <<= 1; return res; }

2. x & -x
3. x & (x - 1) gives x - lowbit(x).

popcount

popcount(x) counts the number of 1-bits.

Calculating popcount

1. Brute force:

   1 2 3 4 5 6 7 8 9 10

   int popcount(int x) { int res = 0; while(x) { res += x & 1; x >>= 1; } return res; }

2. Optimized with lowbit:

   1 2 3 4 5 6

   int popcount(int x) { int res = 0; for(; x; x&=x-1) res ++; return res; }

3. Builtin functions (fastest)

Builtin Bitwise Functions

Note: Functions with ll suffix take long long arguments.

Reference: https://blog.csdn.net/zeekliu/article/details/124848210

__builtin_popcount/__builtin_popcountll

Returns number of 1-bits.

__builtin_ctz / __buitlin_ctzll

Count trailing zeros.

__buitlin_clz / __buitlin_clzll

Count leading zeros.

__builtin_ffs / __buitlin_ffsll

Find position of last set bit (1-indexed).

__builtin_parity / __builtin_parityll

Return parity (even/odd) of 1-bit count.

Applications of Bitwise Operations

Subset Representation

For set {0,1,…,N-1}, use N-bit integer S to represent subsets. Operations:

• Empty set: 0
• Full set: 2ᴺ-1
• Size: __builtin_popcount(S)
• Check element i: S >> i & 1
• Add i: S |= 1 << i
• Remove i (must exist): S ^= 1 << i
• Remove i (any case): S &= ~(1 << i)
• Intersection: S & T
• Union: S | T
• Symmetric difference: S ^ T

Subset Enumeration

- Enumerate all subsets

1

for(int s=0; s<(1<<N); s++)

- Enumerate subsets of a subset

1
2

for(int S=0; S<(1<<N); S++)
    for(int T=S; T; T=(T-1)&S)

Time complexity O(3ᴺ).

- Enumerate K-sized subsets
Optimized method from “Competitive Programming”:

1
2
3
4
5
6
7

int S = (1 << k) - 1;
while(S < 1 << n)
{
    // Process S
    int x = S & -S, y = S + x;
    S = ((S & ~y) / x >> 1) | y;
}

Extension: std::bitset

C++ STL’s bitset for large N:

Exercise: AtCoder ABC 258 G - Triangle

Solution using bitset optimizations. See my explanation.

DFS Optimization with Bitwise Operations

N-Queens problem solved with bitwise optimizations:

Standard backtracking vs. optimized version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Standard backtracking
bool row[maxn], diag_left[maxn << 1], diag_right[maxn << 1];
void dfs(int i) { /* ... */ }

// Bitwise optimized
void dfs(int row, int diag_left, int diag_right)
{
    if(row == mx) { ans++; return; }
    int a = mx & ~(row | diag_left | diag_right);
    while(a) {
        int p = a & -a; a ^= p;
        dfs(row | p, (diag_left | p) >> 1, (diag_right | p) << 1);
    }
}

Performance comparison (for N=16):

• Standard: 53.4s
• Optimized: 6.23s

Exercise: Luogu P1092 [NOIP2004] Alphametic

Other Applications

Swap two numbers

1

void swap(int& a, int& b) { a ^= b ^= a ^= b; }

Average without overflow

1
2

int average1(int x, int y) { return (x >> 1) + (y >> 1) + (x & y & 1); }
int average2(int x, int y) { return (x & y) + ((x ^ y) >> 1); }

Check power of two

1

bool ispowof2(int x) { return x > 0 && !(x & x - 1); }

Conclusion

This article thoroughly explains bitwise operations and their applications.

If you found this helpful, please give a like and share! Thanks for reading!