Howdy, Stranger!

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

Categories

corrected counting bits

bdwbdwbdwbdw 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

Comments

  • IDKIDK 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...

    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]

  • tsagldtsagld 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

  • anthrax11anthrax11 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]
    MOV ebx,ds:[1234];Load the value
    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?
    ADC al,0 ;Add 0 + Carry Flag
    JMP CheckBit
    Done:
    ADC AL,0 ;Check the last bit also
    [/code]
  • tsagldtsagld 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]
    : MOV ebx,ds:[1234];Load the value
    : 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?
    : ADC al,0 ;Add 0 + Carry Flag
    : 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

  • anthrax11anthrax11 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]
    Value: My algo: Your algo:
    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.
  • IDKIDK 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]
    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
    ADC al,0 ;Add 0 + Carry Flag
    }
    [/code]


  • anthrax11anthrax11 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]
    : 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
    : ADC al,0 ;Add 0 + Carry Flag
    : }
    : [/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]


  • IDKIDK 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
    : : ADC al,0 ;Add 0 + Carry Flag
    : : }
    : : [/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]
    :

    Look at my other thread about that...
    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]

  • shaolin007shaolin007 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
    : : : ADC al,0 ;Add 0 + Carry Flag
    : : : }
    : : : [/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]
    : :
    :
    : Look at my other thread about that...
    : 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]

  • tsagldtsagld 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
    : : : ADC al,0 ;Add 0 + Carry Flag
    : : : }
    : : : [/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]
    : :
    :
    : Look at my other thread about that...
    : 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

Sign In or Register to comment.