Number of 1 bits | LeetCode
Iterate 32 times, each time determining if the ith bit is a ’1′ or not. This is probably the easiest solution, and the interviewer would probably not be too happy about it. This solution is also machine dependent (You need to be sure that an unsigned integer is 32-bit). In addition, this solution is not very efficient too, as you need to iterate 32 times no matter what.
Best solution:
We can use x & (x-1) to determine if an integer is a power of two, also every time you perform the operation x & (x-1), a single 1 bit is erased.
// you need to treat n as an unsigned value
// ">>" is signed because it keeps the sign. It uses the most left digit in binary representation of a number as a filler.
// Example:
// 11011011
// >> 11101101
// 01010010
// >> 00101001
// ">>>" is unsigned version of this operator. It always use zero as a filler
// 11011011
// >>> 01101101
// 01010010
// >>> 00101001
public int hammingWeight(int n) {
int result = 0;
while(n != 0) {
result += n & 1;
n = n >>> 1;
}
return result;
}
Read full article from Number of 1 bits | LeetCode
Write a function that takes an unsigned integer and returns the number of '1′ bits it has. For example, the 32-bit integer '11′ has binary representation 00000000000000000000000000001011, so the function should return 3.Brute force solution:
Iterate 32 times, each time determining if the ith bit is a ’1′ or not. This is probably the easiest solution, and the interviewer would probably not be too happy about it. This solution is also machine dependent (You need to be sure that an unsigned integer is 32-bit). In addition, this solution is not very efficient too, as you need to iterate 32 times no matter what.
Best solution:
We can use x & (x-1) to determine if an integer is a power of two, also every time you perform the operation x & (x-1), a single 1 bit is erased.
int number_of_ones(unsigned int x) {
int total_ones = 0;
while (x != 0) {
x = x & (x-1);
total_ones++;
}
return total_ones;
}
https://gist.github.com/gcrfelix/228809f3ef494e95f952// you need to treat n as an unsigned value
// ">>" is signed because it keeps the sign. It uses the most left digit in binary representation of a number as a filler.
// Example:
// 11011011
// >> 11101101
// 01010010
// >> 00101001
// ">>>" is unsigned version of this operator. It always use zero as a filler
// 11011011
// >>> 01101101
// 01010010
// >>> 00101001
public int hammingWeight(int n) {
int result = 0;
while(n != 0) {
result += n & 1;
n = n >>> 1;
}
return result;
}
Read full article from Number of 1 bits | LeetCode
