# Bits manipulations¶

This page include some elegant ways you can use to implement binary strings.

1. Check if a number is a power of 2.

Solution

Typical solution

 1 2 3 4 5 6 7 bool isPow2(int a) { if (a == 0) {return false;} else { while (a % 2 == 0) a /= 2; return (a == 1); } } 

Using bits

Let's try to visualize a power of 2 in binary. It would consist of exactly one "1" digit, so when you subtract 1 from it it would be equivelent to negating it. A negated binary when bitwised-and with the original binary it would give 0.

- 8 13 26 16
a 1000 1101 11010 10000
a-1 0111 1100 11001 01111
a & (a-1) 0000 1100 11000 00000

 1 2 3 bool isPow2(int a) { return (a && !(a & (a-1))); } 
a checks if a != 0, !(a & (a-1)) checks if a-1 is a negation of a.

2. Count # 1's in a binary

Solution

In the previous example we noticed a relation between a, and a-1. That is:

a-1⇔ flipping all digits of a until the first "1".

{a}2 104 116 5
a 1101000 1110100 101
a-1 1100111 1110011 100
a & (a-1) 1100000 1110000 100

Exploiting this observation, each time we bitwise-and a, a-1 we make all digits until the first "1" zeroes.

 1 2 3 4 5 6 7 8 int countOnes(int a) { int count = 0; while (a) { a &= a-1; ++count; } return count; }