Google Interview Question
Developer Program EngineersCountry: United States
public boolean validateByte(int n) {
int rst = 0 ;
while (n != 0) {
n = n & (n - 1);
rst++;
}
return rst == 3 ;
}
By the way, another solution is to do this via a lookup table (you'd have to ask the interviewer how frequently this operation is to be performed though). If frequency and usage of this operation is high, it makes sense to keep in memory all the 8-choose-3 combinations of setting 3 bits from 8. We can then simply do a lookup to return true/false.
This is the second post as the first one does not seem to appear
You can also solve this using the "Hamming Weight" way (check wikipedia)
const char m1 = 0x55; //binary: 0101...
const char m2 = 0x33; //binary: 00110011..
const char m4 = 0x0f; //binary: 4 zeros, 4 ones ...
bool bitCount3(char x) {
x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits
x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits
x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits
return x == 3;
}
public static final int countBits(final byte input, final int lookupBit) {
int counter = 0;
int tmpInput = input;
if (tmpInput != 0) {
while (tmpInput != 0) {
if ((tmpInput & lookupBit) == lookupBit) {
counter++;
}
tmpInput = tmpInput >>> 1;
}
} else {
if (lookupBit == 0) {
counter++;
}
}
return counter;
}
public static final boolean checkIfByteHas3OneBits(final byte input) {
final int oneBits = countBits(input, 1);
return oneBits == 3;
}
public class CheckByteAtLeastNBitsSetToX {
public static void main(String[] args) {
System.out.println(hasAtLeastNBitsSetToX((byte)7, 3, true));
}
public static boolean hasAtLeastNBitsSetToX(byte n, int k, boolean isSet) {
int n1 = n;
int countOnes = 0, countZeros = 0;
while (n1 > 0) {
if ((n1 & 1) > 0) {
countOnes++;
} else {
countZeros++;
}
n1 = n1 >> 1;
}
return isSet? (countOnes >= k) : (countZeros >= k);
}
}
In Java, the simplest way is to use Integer.bitCount(int i):
boolean hasThreeSetBits2(int i) {
return Integer.bitCount(i) == 3;
}
/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
unsigned int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}
Now, we can simply terminate after 3rd iteration (if n is still != 0) & declare the result.
Maximum complexity = 3 operations.
/* Function to check if it has 3 bits */
boolean has3Bits(int n)
{
unsigned int count = 0;
while (n)
{
if(count == 3) return false; //more than 3 bits
n &= (n-1) ;
count++;
}
if(count == 3) return true;
else return false; //less than 3 bits.
}
bool fun(int t) {
- BMW April 13, 2015int num=0;
int one=1;
while (t!=0) {
one=one&t;
if (one==1)
num++;
t=t>>1;
one=1;
}
if (num==3)
return true;
else
return false;
}