Interview Question: Number of Ones in Binary
Vložit
- čas přidán 18. 01. 2016
- Coding interview question from www.byte-by-byte.com/onesinbinary.
In this video, I show how to find the number of ones in the binary representation of a number.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
Need an interview coach? Send in an application: www.byte-by-byte.com/coaching
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
I think you wanted the & bitwise and operator versus ^ exclusive or.
Yep you're right. I added an annotation to the video, but if you don't have annotations enabled you may have missed it
It would be a better idea to just edit your videos at that point where there is a mistake, and may be add a voice-over.
I think it would work better than the annotations. :)
And btw, you are doing great with your coding videos.
Keep it up !!
One quick question...
which editor are u using for these videos ?
and are u on mac or windows ?
yeah that would be great in theory, but youtube won't let you edit an existing video, so unfortunately that's out of the question.
And I use Screenflow on a mac
what about:
ones(x)
count =0
while(x!=0)
if(x%2==1) count++
x=x/2
return count
yep that concept works as well
Want a faster solution for numbers with lot of consecutive 0's in its binary representation? (eg 10000000010000001) Use the fact that x&-x isolate out the rightmost (least significant) set bit of x
int count =0;
while (x>0) {
x^= (x&-x); count++;
}
return count
Basically your run time is proportional to log x, but my run time is proportional to count (the return value)
This is useful to know generally. I suspect you won't be penalized for not knowing this, but you might score extra points for being aware of the property.
there's also a variation that uses x & (x-1) property of 2's complement representation
We can do it without using bit operations also in logn time
class Test {
public static void main(String[] args) {
int n = 6;
int oneCount = 0;
while (n != 0) {
// remainder will be either 0 or 1
oneCount += (n % 2);
n = (n / 2);
}
System.out.println(oneCount);
}
}
Thanks for doing these, Sam.
One caveat here is that negative numbers will produce undesired behaviour here.
Yeah it probably would have been good in retrospect to explicitly handle the case with negative numbers
Can't we just convert a number from decimal to binary and then iterate over the binary representation to compare if each digit is a 0 or 1?
Very good. Thanks.
You're welcome!
Hello! Thank you for your great tutorials. They're very helpful. By the way, I think this method does not work properly for negative input. Instead of using the arithmetic right shift, wouldn't it be better to use the logical right shift and change loop condition to x != 0?
Example:
private static int ones(int number)
{
int sum = 0;
while (number != 0)
{
sum += number & 1;
number >>>= 1;
}
return sum;
}
That's a good catch. I think you're right, that my solution wouldn't work for negative numbers and I like the alternative you gave. Thanks for the input!
Thanks to you for the great tutorials!
Please explain me how the big O notation for this code is log X. See every byte is 8 bit so performance in terms of big O notation is O(4X)
The reason for log(X) is that we are going through each bit of the number once. When you look at a number, the number of bits that it takes to represent a number is log base 2 of that number. In this case, we are considering the bits in the number's representation and not the number itself, so the runtime is O(log X) instead of O(X)
Thank you for the video, but when I'm testing with 5, for example, ^ operation returns me 4 at first iteration next iteration is 2
Yeah as others mentioned, it should be &
What if we go without bitwise operations?
int count(x){
int cnt=0;
while(x != 0)
{
x -= Math.ceil(Math.log(x,2)));
cnt++;
}
return cnt;
}
In terms of computation is it expensive?
Definitely bitwise would be more efficient, but this isn't a bad way to do it, especially if you're not comfortable with bit manipulation
Hey Sam, great video. Correct me if I am wrong but I think you can also use bitwise XOR, just that you can replace 1 with 0 and it should give you the same result. (sum += x ^ 0).
I think that's right
I think this is not correct and the number will be the summation of X because x xor 0s = x
You used the XOR operator bro
hey bitwise exclusive or 0 ^ 0 = 1 1 ^ 1 = 1. So it would give the wrong answer, we could use & bitwise.
Yep that was mentioned below. It was a typo
make more videos sir
in C# ^ is exclusive Or and not Bitwise & so was confused for a moment :-)
So why is nobody talking about doing it string way by comparing characters, cuz its O(n) ?
The output did not make any sense to me. I am lost!
I know it's kinda cheating but you can use __builtin_popcount function if you are using gcc lol
Sum+=X&1
i watched it from mobile first and it screwed me up "^" bitwise and ??? :D thank god annotation
haha