Bitwise Operations in C++
Разница между en4 и en5, 65 символ(ов) изменены
Bitwise operations are one of the most powerful tricks in programming — especially in competitive programming — because they are **fast (O(1))** and help us manipulate numbers efficiently.↵
↵
---↵
↵
### Basics↵
↵
All numbers are stored in **binary form (0s and 1s)** in memory.↵
↵
Each bit has a value:↵
↵
* `0` → OFF↵
* `1` → ON↵
↵
The **last bit** in a signed integer represents the **sign**:↵
↵
* `0` → Positive↵
* `1` → Negative (in two’s complement form → invert bits + add 1)↵
↵
---↵
↵
### Common Bitwise Operators↵
↵
```↵
&   AND        → bit is 1 if both bits are 1  ↵
|   OR         → bit is 1 if any bit is 1  ↵
^   XOR        → bit is 1 if bits are different  ↵
~   NOT        → inverts all bits  ↵
<<  Left Shift → multiply by 2^x  ↵
>>  Right Shift→ divide by 2^x↵
```↵
↵
---↵
↵
### Binary Representation↵
↵
```cpp↵
#include <bitset>↵
#include <iostream>↵
using namespace std;↵
↵
int main() {↵
    int a = 5;↵
    cout << bitset<32>(a) << endl;     // Binary representation of a↵
    cout << bitset<32>(~a) << endl;    // Binary of NOT a↵
}↵
```↵
↵
`bitset<32>` means we represent the number using **32 bits**.↵
↵
---↵
↵
### Turning Bits On / Off / Flip↵
↵
**Turn ON bit x**↵
Make sure bit x = 1 (keep others unchanged):↵
↵
```cpp↵
a = a | (1 << x);↵
```↵
↵
**Explanation:**↵
`(1 << x)` shifts `1` to the left by `x` positions, so it creates a number with **only one bit ON** at position `x`.↵
Then, using the OR `|` operation turns that bit ON without changing the others.↵
↵
---↵
↵
**Turn OFF bit x**↵
Make sure bit x = 0:↵
↵
```cpp↵
a = a & ~(1 << x);↵
```↵
↵
**Explanation:**↵
`(1 << x)` marks the bit you want to turn off.↵
`~` inverts all bits (so that the bit you want to clear becomes `0`, and all others are `1`).↵
Then `&` keeps all bits the same, except that bit `x` becomes `0`.↵
↵
---↵
↵
**Flip bit x**↵
If it’s 1 → 0, if it’s 0 → 1:↵
↵
```cpp↵
a = a ^ (1 << x);↵
```↵
↵
**Explanation:**↵
`^` (XOR) changes a bit only if the bits differ.↵
So this toggles the target bit: `1 → 0`, `0 → 1`.↵
↵
---↵
↵
### Check if bit x is ON↵
↵
Two ways:↵
↵
```cpp↵
if (a & (1 << x)) cout << "ON";↵
else cout << "OFF";↵
```↵
↵
or↵
↵
```cpp↵
if ((a >> x) & 1) cout << "ON";↵
```↵
↵
---↵
↵
### Identity Elements↵
↵
```↵
Identity for AND (&) → all bits = 1 as  (a & -1) = a   as (-1=1111111... )↵
Identity for OR (|)  → all bits = 0 as  (a | 0) = a    as (0=000000000.. )↵
Identity for XOR (^) → all bits = 0 as  (a ^ 0) = a    as (0=000000000.. )↵
↵
```↵
↵
↵
### Important XOR Properties↵
↵
```↵
a ^ a = 0↵
a ^ b = b ^ a↵
(a ^ b) ^ c = a ^ (b ^ c)↵
↵
```↵
↵
↵
---↵
↵
### Even / Odd Check↵
↵
```cpp↵
if (x & 1) cout << "Odd";↵
else cout << "Even";↵
```↵
↵
---↵
↵
### Example: Can a string form a palindrome?↵
↵
Idea: In a palindrome, every letter appears an even number of times — except possibly one.↵
We use XOR to track whether each character appears an odd or even number of times.↵
↵
```cpp↵
string s;↵
cin >> s;↵
int ans = 0;↵
↵
for (char c : s) {↵
    ans ^= 1 << (c - 'a');↵
}↵
↵
// if at most one bit is ON → palindrome possible↵
if (ans == 0 || (ans & (ans - 1)) == 0)↵
    cout << "YES";↵
else↵
    cout << "NO";↵
```↵
↵
**Explanation of `(ans & (ans - 1)) == 0`:**↵
Example:↵
↵
```↵
ans = 1000  ↵
ans - 1 = 0111  ↵
ans & (ans - 1) = 0000↵
```↵
↵
This trick checks whether `ans` has **only one bit ON** (i.e., it’s a power of 2).↵
If a number has just one set bit, subtracting 1 flips all bits **after** that position — so `ans & (ans - 1)` becomes 0.↵
That’s why this condition means “at most one odd-count letter” → palindrome possible.↵
↵
---↵
↵
### Built-in Bit Functions (GCC)↵
↵
```↵
__builtin_popcount(x)    → Count 1s in integer↵
__builtin_popcountll(x)  → Count 1s in long long↵
__builtin_clz(x)         → Count leading zeros↵
__builtin_ctz(x)         → Count trailing zeros↵
__lg(x)                  → Position of the highest bit (≈ floor(log2(x)))↵
```↵
↵
**Explanation:**↵
↵
* `__builtin_clz(x)` → Counts how many zeros come **before the first 1 from the left**.↵
* `__builtin_ctz(x)` → Counts how many zeros come **after the last 1 from the right**.↵
  These are useful to find the **position of the first or last set bit** quickly.↵
↵
---↵
↵
### Example↵
↵
```cpp↵
int x = 8;↵
cout << __builtin_popcount(x) << endl; // 1↵
cout << __lg(x) << endl;               // 3↵
cout << (1 << __lg(x)) << endl;        // 8↵
```↵
↵
---↵
↵
### Summary↵
↵
Turn ON bit:↵
`a = a | (1 << x)`↵
↵
Turn OFF bit:↵
`a = a & ~(1 << x)`↵
↵
Flip bit:↵
`a = a ^ (1 << x)`↵
↵
Check bit:↵
`(a >> x) & 1`↵
↵
Even / Odd:↵
`x & 1`↵
↵
Multiply by 2ˣ:↵
`a << x`↵
↵
Divide by 2ˣ:↵
`a >> x`↵
↵
---↵
↵
**All bitwise operations work in O(1).**↵
Mastering them can make your code shorter, faster, and smarter.↵
↵
---↵
**some notes while solving** ↵
1)↵
XOR with 1 flips the last bit of the number.↵
Even numbers end with 0, so they become 1 (number + 1).↵
Odd numbers end with 1, so they become 0 (number − 1).↵
↵
Some notes while solving:↵
↵
XOR with 1 flips the last bit of a number.↵
Even numbers end with 0, so it becomes 1 (the number increases by 1).↵
Odd numbers end with 1, so it becomes 0 (the number decreases by 1).↵
↵
---
↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Nourhan_Abo-Heba 2026-01-30 20:33:39 65
en4 Английский Nourhan_Abo-Heba 2026-01-30 20:32:08 198
en3 Английский Nourhan_Abo-Heba 2025-10-20 16:47:55 119
en2 Английский Nourhan_Abo-Heba 2025-10-20 15:37:19 168
en1 Английский Nourhan_Abo-Heba 2025-10-20 12:42:46 4491 Initial revision (published)