Author |
Topic: Ones in a register solution (Read 2751 times) |
|
Tom Shields
Guest
|
int ones_in_an_int(int n)
{
int count = 0;
while (n) {
count++;
n = n & (n-1);
}
return count;
}
|
|
 IP Logged |
|
|
|
Marian Szczepkowski
Guest
|
 |
Re: Ones in a register solution
« Reply #1 on: Jul 24th, 2002, 1:19am » |
 Quote  Modify
 Remove
|
Surely something like this
register r = 1;
int count;
for(count = 1; r > 0; count++) {
r=r<<1;
}
return count;
Also works in assembler
1 mov a 0x01
2 mov b 0x01
3 incr b
4 rol a
5 jgt 3
|
|
IP Logged |
|
|
|
Tom Shields
Guest
|
 |
Re: Ones in a register solution
« Reply #2 on: Jul 25th, 2002, 10:36pm » |
Quote Modify
Remove
|
The problem states: "How can you determine the number of ones in an n-bit register only using i iterations, where i is the number of ones in the register?"
Your solution uses n iterations, not i iterations. Also, there's a bug when there are no ones at all.
|
|
IP Logged |
|
|
|
Tom Shields
Guest
|
|
Re: Ones in a register solution
« Reply #3 on: Jul 25th, 2002, 10:38pm » |
Quote Modify
Remove
|
The bug in mine is: I should have used "unsigned" instead of "int". 
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: Ones in a register solution
« Reply #4 on: Jul 27th, 2002, 11:49am » |
Quote Modify
|
The solution comes from the observation that n & (n-1) always has one less bit on than n does (n is an unsigned value).
To show this, say that the lowest-order bit that is a 1 in a value n is at position k:
n = bits 1 0 0 ... 0
k
The difference in bits between n and n-1 is only in bits k and lower:
n-1 = bits 0 1 1 ... 1
k
So:
n & (n-1) = bits 0 0 0 ... 0
k
The & will result in the same higher-order bits, but k and lower are now all 0 - one less than n had.
So the algorithm is:
unsigned int n = ...;
if(n == 0) {
return 0;
}
int count = 1;
while(n = (n & (n-1))) {
count++;
}
return count;
The question that asks how to determine if a value is a power of two in a single statement is a special case of this.
|
|
IP Logged |
|
|
|
cnmne
Guest
|
|
Re: Ones in a register solution
« Reply #5 on: Jul 28th, 2002, 7:01pm » |
Quote Modify
Remove
|
this may not count, but it has no iterations...
int bit32on2( unsigned long a ) { // bitwise reduction tallying
if ( a ) {
register unsigned long temp;
a = ( a & ( temp = 0x55555555 ) ) + ( ( a >> 1 ) & temp );
a = ( a & ( temp = 0x33333333 ) ) + ( ( a >> 2 ) & temp );
a = ( a & ( temp = 0x07070707 ) ) + ( ( a >> 4 ) & temp );
a = ( a & ( temp = 0x000F000F ) ) + ( ( a >> 8 ) & temp );
a = ( a & ( temp = 0x0000001F ) ) + ( ( a >> 16 ) & temp );
}
return a;
}
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
|
Re: Ones in a register solution
« Reply #6 on: Aug 6th, 2002, 11:06pm » |
Quote Modify
Remove
|
Download the Athlon optimization guide:
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/ 22007.pdf
The solution shown there (under "Population Count", page 136, and page 184) is probably the fastest way to do it in x86 processors, or in standard C. (Other processors have popcount instructions, which would clearly be the fastest way for those platforms.)
The basic idea is to take 3 bits at a time, and translating them to the number of 1 bits among them in parallel using logical operations, then summing those partial results.
|
|
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Ones in a register solution
« Reply #7 on: Jul 12th, 2004, 9:23am » |
Quote Modify
|
Extending the approach, if you had to do it a lot of times in software:
Prepare a 256 element array 'ones', in advance where ones[i] = number of 1's in the representation of i and where i ranges from 0 to 255.
Now, for each 32 bit number x,
unsigned char *cp = (unsigned char *) &x.
return ones[*cp] + ones[*(cp+1)] + ones[*(cp+2)] + ones[*(cp+3)];
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print