mirror of
https://github.com/Manoj-HV30/dsa-competitive-programming.git
synced 2026-05-16 19:35:22 +00:00
19 lines
512 B
C++
19 lines
512 B
C++
class Solution{
|
|
public:
|
|
int hammingWeight(int n){
|
|
int res= 0;
|
|
/*for(int i = 0;i<32;i++){
|
|
if(n>>i && 1) res ++;
|
|
}*/
|
|
|
|
//brian-kernighan's algo
|
|
while(n){
|
|
n = n&(n-1);
|
|
res++
|
|
|
|
}
|
|
return res;
|
|
}
|
|
};
|
|
//n&n-1 resets the last set bit to 0, brian's algo takes o(number of set bits to run) unlike brute force which takes o(total no. of bits). both are o(1).
|