Google Interview Question Software Engineer / Developers
Country: United States
Forgot to mention that this has the advantage of being O(log(n)) rather than O(n) in the number of bits used by value type.
This would have many more upvotes if anyone except a couple people understood what's happening here.
We're taking all the odd bits and all the even bits, and then shifting the odd bits over so they're in the even positions. So if we had (for 8 bits, say), 11010011, we'd now have 10000010 (odd bits) >> 1 = 01000001, and 01010001 (even bits). Now we'll just add the two, but because of the way this has been structured, there's guaranteed space for the carries.
So we end up with 10 01 00 10. Each group of 2 digits here represents the count of 1s in the corresponding two digits. Now we add each group of 2 digits together
10 00 00 00 (odd groups of 2 - 1st, 3rd groups of 2) >> 2 = 00 10 00 00
00 10 00 00
00 01 00 10 (even groups of 2 - 0th, 2nd groups of 2)
------------
0011 0010
Each group of 4 has the count of 1s in that group of 4 bits.
A final step will similarly sum 0011 + 0010 = 0101. This is the final answer of 5 set bits.
I'm still impressed by how clever this trick is.
int count=0;
while(n>0){
//n-1 will set the right most set bit to zero. AND with the same number will sustain the remaining bits
n&=n-1;
count++;
}
the value of count gives the number of count bits.
And then I think the question wants you to cache that value to speed up the process in case the function is called with the same input again.
Nicely done. But, do you need to & with (n-1). Can't you & with 1?
Something like this?
public class F {
private static final int NUM = 85;
public static void main(String[] args) {
int num = NUM;
int count = 0;
int x = 0;
while (num > 0) {
count = count + (num & 1);
num = num >> 1;
}
System.out.println("Count = " + count);
}
}
class Test{
public static void main(String args[]){
System.out.println("Enter number");
Scanner scanner=new Scanner(System.in);
int number=scanner.nextInt();
int count=0;
while(number>0){
if(number%2!=0)
count++;
number/=2;
}
System.out.println("number of set bits are:"+count);
}
The complexity would be O(logn).
could you explain why shifting the number right is logn complexity? worst case you'll shift all bits, which is O(n)
I think the key here is to improve time second time via "unlimited memory". Means interviewer tried to get better complexity second time. It's possible to achieve O(1) complexity second time if we use enourmous ammount of memory, by allocating an array with type max value size, for int that would be 0xffffffff, which is ~16GB at 32 bit machine which is impossible to address. But we have unlimited memory, so here's the code. The way to make it real is use bitset for cache, as we need only 5 bits to store bits count for 32 bit type.
size_t cache[0xffffffff] = {0};
size_t countBits(unsigned int i) {
if(i == 0) return 0;
// cache lookup in O(1)
size_t count = 0;
if(cache[i] != 0)
return cache[i];
// calculate
while(i > 0) {
i &= i - 1;
count++;
}
// and cache the result
cache[i] = count;
return count;
}
Suppose, the number n is 7 (in binary 0111) and n-1 will be 6 (0110)
n&=n-1 in the first iteration will be 6 (count incremented to 1)
in the second iteration it will be (0100) count incremented to 2 and in the third iteration n will be 0000 and count incremented to 3 and the loop exits as n will go less than 0 after this. Now, the count has the number of bits set.
- Simon September 04, 2012uint bit_count(uint value) { printf("0x%08X has ", value, value); value = (value & 0x55555555) + ((value & 0xaaaaaaaa) >> 1); value = (value & 0x33333333) + ((value & 0xcccccccc) >> 2); value = (value & 0x0F0F0F0F) + ((value & 0xF0F0F0F0) >> 4); value = (value & 0x00FF00FF) + ((value & 0xFF00FF00) >> 8); value = (value & 0x0000FFFF) + ((value & 0xFFFF0000) >> 16); printf("%d bits set.\n", value); return value; }