Problem:
Count 1 in 32 bits
00000000000000000000000000001110
answer is 3.
Bruteforce approach
iterate from whole bit and count 1.
if input is n bits, the answer is O(n)
Better approach
Utilizing bit operation.
x is the input.
x - 1 would find the first set bit from the end, and then set it to 0, and set all the bits following it.
Which means if x = 10101001010100
^
|
|
|
First set bit from the end
Then x - 1 becomes 10101001010(011)
This approach is O(m). m is the number of 1 in the bits
#include<iostream>
#include<bitset>
using namespace std;
int main(){
// 11111 in bits
unsigned int x = 15;
int total = 0;
while (x != 0){
cout << x << endl;
bitset<32> a1(x);
cout << a1 << endl;
bitset<32> a2(x - 1);
cout << a2 << endl;
x = x & (x - 1);
total++;
bitset<32> a3(x);
cout << a3 << endl;
}
cout << total << endl;
}
15
// x
00000000000000000000000000001111
// x - 1
00000000000000000000000000001110
// x & (x - 1)
00000000000000000000000000001110
14
// x
00000000000000000000000000001110
// x - 1
00000000000000000000000000001101
// x & (x -1)
00000000000000000000000000001100
12
// x
00000000000000000000000000001100
// x - 1
00000000000000000000000000001011
// x & (x - 1)
00000000000000000000000000001000
8
// x
00000000000000000000000000001000
// x - 1
00000000000000000000000000000111
// x & (x - 1)
00000000000000000000000000000000
4