Now I am writing an article about bit manipulation, bit magic and other trciks for wiki — conspects (This is a great resource of algorithms in Russian). If you know some useful bit tricks, which used in algoritms or just funny things connected with bits write them in comments below. Also you are welcomed with really strange, weird and sophisticated solutions for well-known problems. For example: swapping values with XOR.

Good style for your comments:

- Descripotion of the problem
- Solution of the problem in code with short explanation for tricky moments

Example of a perfect comment:

**Determining if an integer is a power of 2**

```
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
```

**Short explanation**: Let v — power of two (this is one and k zeros in binary presentation) and v — 1 is k ones in binary presenation. Then notice that bitwise AND v and v — 1 must be 0.

**Warm — up problem**: Find smallest 1 — bit (not zero) in O(1)

Zero is not a power of two. Your code says otherwise :)

Yeah.

2

^{32}= 0or:

f = __builtin_popcount(v) == 1;

This method is much slower.

Smallest bit set to 1 of an integerExplanation: -number representation using 2-complement keeps the smallest 1-bit and inverts the other most significative bits.

Unsetting the smallest 1-bit of an integerint number = 123; number -= number & -number;

Counting the number of bits set to 1Toggle bit i from 1->0 or 0->1Xor with bit set to 1, makes it change its value, whereas the other bits are 0 and don't change anything.

Iterate all subsets of a bitmask in increasing orderIterate all subsets of a bitmask in decreasing orderCan u plz give a small example for "Iterate all subsets of a bitmask in increasing order". It is not clear to me... :/

Swap two integersCheck whether two integers are equal or not:Check if a equals -1 or notGet the largest number I can!For the least numberOperation x & (x — 1) sets rightmost 1 to 0. As powers of 2 have only one 1 — it can be used to check them.

My favorite is binary searching by bit manipulation — no off-by-1 errors!

Original source: https://github.com/pathikrit/scalgos/tree/master/src/main/scala/com/github/pathikrit/scalgos

Could you explain please what

`Seq(p, n) find f`

means?`p`

and`n`

are numbers in`[0, Long.MaxValue]`

and`[Long.MinValue, 0]`

respectively for which f maybe satisfactory.`Seq(p, n)`

creates a sequence of these 2 numbers and`Seq(p, n) find f`

returns the first one for which f is true else None. I am using Scala as my language; here's a Java/C++-ish version (not tested):Can someone provide links to the problems, where you need a fast way to count number of 1's in mask or index of last setted bit?

633G - Yash And Trees