#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# corrected counting bits

Member Posts: 4
:Sorry about the mistake and thanks for the input.

My question reads, "Count the number of bits, in a double word that starts at memory location DS:1234h, that are 1. Place the count in register AL.
Can you explain the process or give me some examples, but please don't give me the answer to the above problem , I need to do that one myself.

THANK YOU

• Member Posts: 1,784
: :Sorry about the mistake and thanks for the input.
:
: My question reads, "Count the number of bits, in a double word that starts at memory location DS:1234h, that are 1. Place the count in register AL.
: Can you explain the process or give me some examples, but please don't give me the answer to the above problem , I need to do that one myself.
:

Good that someone understands the meaning of learning...

How would you do it with by hand?
This is the easiest way of solving a problem...

I would convert it to binary, but the computer already got it in binary so it isn't needed.

Then simply count the number of ones like this:
Start at some end and get the binary digit.
If it's a one increse a number.
Then do go to the next number and do the same until your finnished.

Happy coding wishes
the one and only
[b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]

• Member Posts: 621
: : :Sorry about the mistake and thanks for the input.
: :
: : My question reads, "Count the number of bits, in a double word that starts at memory location DS:1234h, that are 1. Place the count in register AL.
: : Can you explain the process or give me some examples, but please don't give me the answer to the above problem , I need to do that one myself.
: :
:
: Good that someone understands the meaning of learning...
:
: How would you do it with by hand?
: This is the easiest way of solving a problem...
:
: I would convert it to binary, but the computer already got it in binary so it isn't needed.
:
: Then simply count the number of ones like this:
: Start at some end and get the binary digit.
: If it's a one increse a number.
: Then do go to the next number and do the same until your finnished.
:
: Happy coding wishes
: the one and only
: [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]
:
:

There is a lightning fast algorithm to count set bits, here it is in pseudeo- c++:
[code]
int AL = 0;
int EBX = [1234]
while ( EBX != 0)
{
EBX &= (EBX - 1);
AL++;
}
[/code]

Greets,
Eric Goldstein
www.gvh-maatwerk.nl

• Member Posts: 511
: : : :Sorry about the mistake and thanks for the input.
: : :
: : : My question reads, "Count the number of bits, in a double word that starts at memory location DS:1234h, that are 1. Place the count in register AL.
: : : Can you explain the process or give me some examples, but please don't give me the answer to the above problem , I need to do that one myself.
: : :
: :
: : Good that someone understands the meaning of learning...
: :
: : Now to your problem:
: : How would you do it with by hand?
: : This is the easiest way of solving a problem...
: :
: : I would convert it to binary, but the computer already got it in binary so it isn't needed.
: :
: : Then simply count the number of ones like this:
: : Start at some end and get the binary digit.
: : If it's a one increse a number.
: : Then do go to the next number and do the same until your finnished.
: :
: : Happy coding wishes
: : the one and only
: : [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]
: :
: :
:
: There is a lightning fast algorithm to count set bits, here it is in pseudeo- c++:
: [code]
: int AL = 0;
: int EBX = [1234]
: while ( EBX != 0)
: {
: EBX &= (EBX - 1);
: AL++;
: }
: [/code]
:
: Greets,
: Eric Goldstein
: www.gvh-maatwerk.nl
:
:
Well, that's practically the same as I suggested before:
[code]
XOR al,al ;Clear al

CheckBit:
SHR ebx,1 ;CF holds the bit that was shifted out by shr
JZ Done ;Any more bits set?
JMP CheckBit
Done:
ADC AL,0 ;Check the last bit also
[/code]
• Member Posts: 621
: : : : :Sorry about the mistake and thanks for the input.
: : : :
: : : : My question reads, "Count the number of bits, in a double word that starts at memory location DS:1234h, that are 1. Place the count in register AL.
: : : : Can you explain the process or give me some examples, but please don't give me the answer to the above problem , I need to do that one myself.
: : : :
: : :
: : : Good that someone understands the meaning of learning...
: : :
: : : Now to your problem:
: : : How would you do it with by hand?
: : : This is the easiest way of solving a problem...
: : :
: : : I would convert it to binary, but the computer already got it in binary so it isn't needed.
: : :
: : : Then simply count the number of ones like this:
: : : Start at some end and get the binary digit.
: : : If it's a one increse a number.
: : : Then do go to the next number and do the same until your finnished.
: : :
: : : Happy coding wishes
: : : the one and only
: : : [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]
: : :
: : :
: :
: : There is a lightning fast algorithm to count set bits, here it is in pseudeo- c++:
: : [code]
: : int AL = 0;
: : int EBX = [1234]
: : while ( EBX != 0)
: : {
: : EBX &= (EBX - 1);
: : AL++;
: : }
: : [/code]
: :
: : Greets,
: : Eric Goldstein
: : www.gvh-maatwerk.nl
: :
: :
: Well, that's practically the same as I suggested before:
: [code]
: XOR al,al ;Clear al
:
: CheckBit:
: SHR ebx,1 ;CF holds the bit that was shifted out by shr
: JZ Done ;Any more bits set?
: JMP CheckBit
: Done:
: ADC AL,0 ;Check the last bit also
: [/code]
:
It's entirely different. Your algo takes as much iterations as the number of the highest bit set.
If, for example, EBX = 0x80000000, your algo takes 32 iterations, while the one I presented takes only one.
Look closer, the two algo's are entirely different.

Greets,
Eric Goldstein
www.gvh-maatwerk.nl

• Member Posts: 511
: It's entirely different. Your algo takes as much iterations as the number of the highest bit set.
: If, for example, EBX = 0x80000000, your algo takes 32 iterations, while the one I presented takes only one.
: Look closer, the two algo's are entirely different.
:
:
: Greets,
: Eric Goldstein
: www.gvh-maatwerk.nl
:
:
Sorry, I didn't realise at first.
Friday, after school, got bored, converted the pseudo-code to assembly, compiled with MASM32, looped both the algos 100 million times, and i must say your algo is a lot faster. I was kind of hoping that my algorithm would be faster for numbers with many set bits, but I was wrong. Here are the results on my PII 350mhz:
[code]
0FFFFFFFFh 35 seconds 19 seconds
NULL 2 seconds 1.5 seconds
0C0C0C0C0h 41 secons(ugh!) 16 seconds
0CCCCCCCCh 34 seconds 28 seconds
[/code]
The results will surely differ for processors /w different architectures, but I guess it's safe to say your code is better.
• Member Posts: 1,784
[b][red]This message was edited by IDK at 2006-2-10 7:22:38[/red][/b][hr]

He didn't want any code...

If you unrolled the code it would be very much faster.

Try this:
[code]
XOR al,al ;Clear al

rept 16 {
SHR ebx,1 ;CF holds the bit that was shifted out by shr
}
[/code]

• Member Posts: 511
[b][red]This message was edited by anthrax11 at 2006-2-10 8:38:4[/red][/b][hr]
: [b][red]This message was edited by IDK at 2006-2-10 7:22:38[/red][/b][hr]
:
: He didn't want any code...
:
:
: If you unrolled the code it would be very much faster.
:
: Try this:
: [code]
: XOR al,al ;Clear al
:
: rept 16 {
: SHR ebx,1 ;CF holds the bit that was shifted out by shr
: }
: [/code]
:
:
That's the dilemma in programming, choosing between small code and fast code. But notice, that unrolling the loop and removing the code that checks if bx!=0 results in having 32 iterations for any dword. Plus the extra code will have to be read into the cache memory each time. So take your pick:-D:
[code]
Value: My algo: tsagld's algo: IDK's algo:
0FFFFFFFFh 35 secs 19 secs 22 secs
NULL 2 secs 1.5 secs 23 secs
0C0C0C0C0h 41 secs 16 secs 22 secs
0CCCCCCCCh 34 secs 28 secs 22 secs

And finally a category where my algorithm ruled:
0000FFFFh 19 secs 29 secs 22 secs
[/code]

• Member Posts: 1,784

: : He didn't want any code...
: :
: :
: : If you unrolled the code it would be very much faster.
: :
: : Try this:
: : [code]
: : MOV ebx,ds:[1234];Load the value
: : XOR al,al ;Clear al
: :
: : rept 16 {
: : SHR ebx,1 ;CF holds the bit that was shifted out by shr
: : }
: : [/code]
: :
: :
: That's the dilemma in programming, choosing between small code and fast code. But notice, that unrolling the loop and removing the code that checks if bx!=0 results in having 32 iterations for any dword. Plus the extra code will have to be read into the cache memory each time. So take your pick:-D:
: [code]
: Value: My algo: tsagld's algo: IDK's algo:
: 0FFFFFFFFh 35 secs 19 secs 22 secs
: NULL 2 secs 1.5 secs 23 secs
: 0C0C0C0C0h 41 secs 16 secs 22 secs
: 0CCCCCCCCh 34 secs 28 secs 22 secs
:
: And finally a category where my algorithm ruled:
: 0000FFFFh 19 secs 29 secs 22 secs
: [/code]
:

There I found an algorithm for MUL faster than the proccessors MUL...
But only for the best case senario. The other where very much slower.

This is the rather the same. You don't win much performance but gain a lot in memmory in your code. Your code only took 3 seconds faster on it's fastest.

In a way one could say that my version was the best, becouse its worste case was the lowest... My algorihtm in big O should be O(0) I think, wich is what most try to do...

Personaly I think tsagld algo is the best...

Happy coding wishes
the one and only
[b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]

• Member Posts: 1,018
:
: : : He didn't want any code...
: : :
: : :
: : : If you unrolled the code it would be very much faster.
: : :
: : : Try this:
: : : [code]
: : : MOV ebx,ds:[1234];Load the value
: : : XOR al,al ;Clear al
: : :
: : : rept 16 {
: : : SHR ebx,1 ;CF holds the bit that was shifted out by shr
: : : }
: : : [/code]
: : :
: : :
: : That's the dilemma in programming, choosing between small code and fast code. But notice, that unrolling the loop and removing the code that checks if bx!=0 results in having 32 iterations for any dword. Plus the extra code will have to be read into the cache memory each time. So take your pick:-D:
: : [code]
: : Value: My algo: tsagld's algo: IDK's algo:
: : 0FFFFFFFFh 35 secs 19 secs 22 secs
: : NULL 2 secs 1.5 secs 23 secs
: : 0C0C0C0C0h 41 secs 16 secs 22 secs
: : 0CCCCCCCCh 34 secs 28 secs 22 secs
: :
: : And finally a category where my algorithm ruled:
: : 0000FFFFh 19 secs 29 secs 22 secs
: : [/code]
: :
:
: There I found an algorithm for MUL faster than the proccessors MUL...
: But only for the best case senario. The other where very much slower.
:
: This is the rather the same. You don't win much performance but gain a lot in memmory in your code. Your code only took 3 seconds faster on it's fastest.
:
: In a way one could say that my version was the best, becouse its worste case was the lowest... My algorihtm in big O should be O(0) I think, wich is what most try to do...
:
: Personaly I think tsagld algo is the best...
:
: Happy coding wishes
: the one and only
: [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]
:
:
[green]
Hey, just use whatever works for you. I mean, you should always try and improve upon your code but all those algorithms are pretty good in the long run. My main thing is program size. Usually if the size is small the program is fast. They kind of go hand-in-hand so to speak. Hey you guys ought to try some of those contests where the program can be only 512bytes tops and runs the fastest out of the bunch. You would probably do well all of you! :-)
[/green]

• Member Posts: 621
:
: : : He didn't want any code...
: : :
: : :
: : : If you unrolled the code it would be very much faster.
: : :
: : : Try this:
: : : [code]
: : : MOV ebx,ds:[1234];Load the value
: : : XOR al,al ;Clear al
: : :
: : : rept 16 {
: : : SHR ebx,1 ;CF holds the bit that was shifted out by shr
: : : }
: : : [/code]
: : :
: : :
: : That's the dilemma in programming, choosing between small code and fast code. But notice, that unrolling the loop and removing the code that checks if bx!=0 results in having 32 iterations for any dword. Plus the extra code will have to be read into the cache memory each time. So take your pick:-D:
: : [code]
: : Value: My algo: tsagld's algo: IDK's algo:
: : 0FFFFFFFFh 35 secs 19 secs 22 secs
: : NULL 2 secs 1.5 secs 23 secs
: : 0C0C0C0C0h 41 secs 16 secs 22 secs
: : 0CCCCCCCCh 34 secs 28 secs 22 secs
: :
: : And finally a category where my algorithm ruled:
: : 0000FFFFh 19 secs 29 secs 22 secs
: : [/code]
: :
:
: There I found an algorithm for MUL faster than the proccessors MUL...
: But only for the best case senario. The other where very much slower.
:
: This is the rather the same. You don't win much performance but gain a lot in memmory in your code. Your code only took 3 seconds faster on it's fastest.
:
: In a way one could say that my version was the best, becouse its worste case was the lowest... My algorihtm in big O should be O(0) I think, wich is what most try to do...
:
: Personaly I think tsagld algo is the best...
:
: Happy coding wishes
: the one and only
: [b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]
:
:

I'd like to point out that the algo is not mine. It was thought of by some computer science prof a while ago.
When I saw the algo the first time, I was stunned by its brilliantness. It only takes as much iterations as the number of set bits, regardless what bits. Brilliant...

Greets,
Eric Goldstein
www.gvh-maatwerk.nl