Printable View
I'm having a trouble of thinking of way to count the number of 1 bits in a binary number with out using any condition tests or branches. Only ones i know have condition tests or branches like
This is for my assembly language class and I'm supposed to use any kind of shifting or and/or. But if I saw it in C++ i probably be able to convert it.Code:while (n!=0)
{
count++;
n=n&(n-1)
}
Oooh! Pick me!
Sorry but I dont think it will work, I forgot to mention I need to count 8-bits :(Quote:
Originally Posted by Dave_Sinkula
(1 << n) is a mask for bit #n.
(number & mask) == 0 when the bit is 0.
(number & mask) != 0 when the bit is 1.
Now loop for each bit from 0 to 7, checking if each is 1.
Code:int num = 46;
int bit = 1;
int count = 0;
while (bit <= 128)
{
count += ((num & bit) > 0);
bit <<= 1;
}
cout << "Has " << count << " bits." << endl;
Me too, me too!Code:unsigned char count foo( unsigned char b )
{
return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8))+
(!!(b& 16))+(!!(b& 32))+(!!(b& 64)0+(!!(b&128));
}
What does the !! mean? And is this for 128 bits? and if i wanted 8 bits I would useQuote:
Originally Posted by quzah
return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8)))
No. It's for eight bits. Just like you wanted. ! is the the "not" operator. That means, if something is non-zero, it becomes zero. Otherwise, it becomes 1. We apply it twice, to make it "change non-zero to zero and then to one".
Otherwise, without it, you just end up with whatever value you origionally pass to the function.
Quzah.
Here's a hint: Powers of 2.Quote:
Originally Posted by gqchynaboy
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
Range from 0-7: 8. Therfore, Quzah is correct in his statement - he is covering all 8 bits in a byte.
Let's face it though - my solution is more elegant.
Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?
Quzah
I'm always finding myself torn between efficiency and elegance, but for such a trivial problem you may as well just plump for elegance.Quote:
Originally Posted by quzah
I want simplicity =]
Simple, elegant, and about as fast as it gets. Next?
:DCode:int bits[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3,
3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,
3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4,
4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5,
5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7,
6, 7, 7, 8
};
int count ( unsigned char x )
{
return bits[x];
}
:cool:Quote:
Originally Posted by Prelude
For extra brownie points you could compute the look-up table beforehand instead of manually bashing it out. For any more bits than this, you'd need to!!!
>For extra brownie points you could compute the look-up table
>beforehand instead of manually bashing it out.
For extra leetness points, I'll let it slip that this table was code generated for a specific number of bits by a tool that I wrote some time ago, not hand crafted. ;)
Good stuff...
In your quest to let everyone know your penis size is bigger than everyone elses, you missed the entire point of my code. I don't care how you do it. I was simply providing yet another FUN variant. I don't really give a ........ what way you do it. I was just showing another interesting variant.
Some people are so ... eh.
Quzah.
Quote:
Originally Posted by quzah
So it would go something like this
i would have b be an int though
b = 1111 1111
(1111 1111 & 1) = 0000 0000
!(0000 0000) = F F
!(0000 0000) = 0 0
No. It would go like this:
1111 1111 & 0000 0001 = 0000 0001
1111 1111 & 0000 0010 = 0000 0010
...
1111 1111 & 1000 0000 = 1000 0000
To further:
1111 1111 & 0000 0001 = 0000 0001
!0000 0001 = 0000 0000
!0000 0000 = 0000 0001
1111 1111 & 0000 0010 = 0000 0010
!0000 0010 = 0000 0000
!0000 0000 = 0000 0001
! non-zero = 0
! 0 = 1
Quzah.
Quote:
Originally Posted by quzah
Oppz i added instead of and..thx man!!!
!0000 0010 = 0000 0000
!0000 0000 = 0000 0001
! non-zero = 0
! 0 = 1
One thing I dont understand how the NOT operator can turn a 2 into 0 then using the NOT again it turns the 0 into 1.
! (0000 0010) = 1111 1101
! (1111 1101) = 0000 0010
thats wat i thought the NOT operator does
Well you can not believe me, or you can simply try it yourself.
I don't care either way. I've already explained how it works. Believe me or don't. I really don't care.Code:cout << "! 2 is " << !2;
Quzah.
No need for attitude, like i said im working in Assembly Langauge and I guess the NOT operator works differently.Quote:
Originally Posted by quzah
Well how many times do you want me to explain it with you saying it doesn't work that way, and me telling you it does, before you actually believe me? What did you expect me to do, tell you I was lying? You either believe it or don't. Either way, like I said, I don't care.
However, if you can't use AND OR or shifting, just take modulus of 2, and see if it is 1 or not. If so, increment the "bit count" counter, and then divide the number by two. If you run out of number to divide, you're done.
But hey, don't take my word for it...
Quzah.
it may be more elegant, but it breaks the number 1 rule of this thread. NO CONDITIONAL TESTS!.Quote:
Originally Posted by samGwilliam
edit: HA HA! i didn;t realize there was a page 2
Bytes and Nibbles,
Anybody feel hungry at this moment in time?
:D
Good point, but I thought a loop would be permitted.Quote:
Originally Posted by misplaced
he used a loop as an example of what he can't use!Quote:
Originally Posted by samGwilliam
Whoops...Quote:
Originally Posted by misplaced
Prelude's code reminds me of a question, the sort of question Microsoft asks you on an interview: If you had to write code to convert ints to roman numerals optimized for speed but with infinite memory, how do you do it? Just store the roman numerals in a table and return the one at the index. Constant runtime :)