Counting Set Bits

[veronicak5678]

I am trying to write a subprocedure that will count the number of buts set in a 16bit number, then send that number (bits set) back to the main procedure in AX. The main should display display the number of 1s and determine if the number is even or odd.

I am trying to count the 1s by shifting left and incrementing on carry. The problem seems to be that when I get back to 'main,' the original input number is still in AX rather than the count I got in 'parity.' I don't know why it isn't changing.

Code Select Expand

;===================================================================
;                   MAIN.ASM
;===================================================================
         EXTERN  GETDEC$:FAR
         EXTERN  NEWLINE:FAR
         EXTERN  PUTSTRNG:FAR
         EXTERN  PUTDEC$:FAR
         EXTERN  PUTBIN:FAR
         EXTERN  PARITY:FAR
;===================================================================
        .MODEL  LARGE
        .STACK  512
;===================================================================
; D A T A   S E G M E N T   D E F I N I T I O N
        .DATA
NUMBER     DW  ?
PROMPT DB 'Enter a number: '
BINDISPLAY    DB 'Number in binary: '
ONESDISPLAY    DB 'Number of 1s: '
ODDDISPLAY    DB 'The number of 1s is odd. '
EVENDISPLAY DB 'The number of 1s is even. ' 
;===================================================================
; C O D E   S E G M E N T   D E F I N I T I O N
        .CODE
        ASSUME  DS:DGROUP
;===================================================================

MAIN    PROC

        MOV     AX,DGROUP           ;SET DS-REGISTER TO POINT TO
        MOV     DS,AX               ;DATA SEGMENT
        MOV     ES,AX               ;AND ES ALSO

        CALL    NEWLINE
        MOV     DI, OFFSET PROMPT
        MOV     CX, SIZEOF PROMPT
        CALL    PUTSTRNG
        CALL    GETDEC$
        CALL    NEWLINE
        MOV     DI, OFFSET BINDISPLAY
        MOV     CX, SIZEOF BINDISPLAY
        CALL    PUTSTRNG
CALL PUTBIN
        PUSH    AX
        CALL    PARITY
CALL NEWLINE


        CALL    NEWLINE
        MOV     DI, OFFSET ONESDISPLAY
        MOV     CX, SIZEOF ONESDISPLAY
        CALL    PUTSTRNG
POP AX
        CALL    PUTDEC$
        CALL    NEWLINE
               
SUB DX, DX
        MOV     BX, 2
        DIV     BX
        CMP     DX, 0
        JNE     ODDS

        MOV     DI, OFFSET EVENDISPLAY
        MOV     CX, SIZEOF EVENDISPLAY
        CALL    NEWLINE
        CALL    PUTSTRNG
        JMP     EXIT_PROGRAM
ODDS:   
        MOV     DI, OFFSET ODDDISPLAY
        MOV     CX, SIZEOF ODDDISPLAY
        CALL    NEWLINE
        CALL    PUTSTRNG       
EXIT_PROGRAM:
.EXIT
        MOV     AX, 4C00H
        INT     21H
MAIN    ENDP
        END MAIN



Code Select Expand

;;===================================================================
;              Veronica Kaufman
;                 CISP 310
;                PARITY.ASM
;===================================================================
         .MODEL  LARGE     
;===================================================================
; D A T A   S E G M E N T   D E F I N I T I O N
        .DATA
ONES_COUNT     DW      0                           
;===================================================================
; C O D E   S E G M E N T   D E F I N I T I O N
        .CODE   
        ASSUME  DS:DGROUP
;===================================================================

PARITY  PROC    FAR PUBLIC USES CX DX DS
POP AX
NUM_LOOP:
CMP AX, 0
JE END_PROGRAM
SHL AX, 1
JC INCREMENT
JMP NUM_LOOP
INCREMENT:
INC ONES_COUNT
JMP NUM_LOOP
END_PROGRAM:
MOV AX, ONES_COUNT
PUSH AX
RET
PARITY  ENDP
        END PARITY

[dedndave]

i dunno how it ever returns at all - lol
when you POP AX, you will get the procedure's return address into AX
this is a far procedure, so just above the return address is also the return segment
just put the value in AX and make the call - it will be in AX when you get there
also, i would avoid using names like PARITY, make it CkParity or something unique

oops! - lol

you are using
PARITY  PROC    FAR PUBLIC USES CX DX DS
so, besides the return address and segment, the assembler also pushes cx, dx, and ds
i have no idea what order they are saved in, but one of those values winds up in ax
i would do something like this...

mov  ax,TestVal
call CkParity
.
.
.
CkParity PROC

xor  dx,dx
mov  cx,16

CkParity0:
shr  ax,1
jnc  BitCounted

inc  dx          ;note - INC does not alter the carry flag

BitCounted:
rcr  bx,1
loop CkParity0

xchg ax,bx       ;original value back in ax
or   ax,ax       ;sets parity flag if odd parity

it isn't necessary to use the parity flag at the end - the count in dx (specifically, bit 0 of dx) tells you even or odd

[jj2007]

ADC is also a pretty useful opcode:

Code Select Expand

include \masm32\include\masm32rt.inc

.code
start:
push 0
call CtBits
print str$(eax), " bits set", 13, 10

push -1
call CtBits
print str$(eax), " bits set", 13, 10

push 01110111000101000111011100010100b
call CtBits
print str$(eax), " bits set", 13, 10

getkey
exit

CtBits proc uses ecx edx arg
mov edx, arg
xor eax, eax
mov ecx, 32 ; put 16 for testing 16 bits only
@@: shl edx, 1
adc eax, 0
dec ecx
jne @B
  ret
CtBits endp
end start


[dedndave]

hiyas Jochen - good idea
just - needs to be in 16-bit form - lol    :P
(16-bit forum)

    mov dx, arg
    xor ax, ax
    mov cx, 16

@@: shl dx, 1
    adc ax, 0
    dec cx
    jne @B

[sinsi]

Code Select Expand


mov ecx, 32 ; put 16 for testing 16 bits only
@@: shl edx, 1

If the count is 16, you should use SHR to count the bottom 16 bits.

[japheth]

Code Select Expand


mov ecx, 32 ; put 16 for testing 16 bits only
@@: shl edx, 1

If the count is 16, you should use SHR to count the bottom 16 bits.

or simply use no count at all:

Code Select Expand


CtBits proc uses edx arg
mov edx, arg
xor eax, eax
@@: shr dx, 1
adc eax, 0
and dx, dx
jne @B
ret
CtBits endp


[dedndave]

even better Japheth
but, this is still the 16-bit forum - lol

CtBits  proc uses bx dx arg

        mov     dx,arg
        xor     ax,ax
        mov     bx,ax

@@:     shr     dx,1
        adc     ax,bx
        and     dx,dx
        jne     @B

        ret

CtBits  endp

[jj2007]

Code Select Expand


mov ecx, 32 ; put 16 for testing 16 bits only
@@: shl edx, 1

If the count is 16, you should use SHR to count the bottom 16 bits.

You are right, as usual :U

Here is an example how it could be done with a macro. Very flexible but 32 bit code.

Code Select Expand

include \masm32\include\masm32rt.inc

PopCount MACRO arg
LOCAL testReg, ctReg, size
size = 32
if @SizeStr(<arg>) eq 2
size = 16
endif
ctReg equ ecx
if @InStr(1, <arg>, <ax>)
testReg equ <edx>
else
testReg equ <eax>
if @InStr(1, <arg>, <cx>)
ctReg equ edx
endif
endif
; int 3
push testReg
xor testReg, testReg
push ctReg
push size
pop ctReg
@@: rol arg, 1
adc testReg, 0
dec ctReg
jne @B
pop ctReg
xchg dword ptr testReg, [esp]
pop eax
; int 3
EXITM <eax>
ENDM

.code
start:
print "Counting bits in a proc: ", 13, 10
push 0
call CtBits
print str$(eax), " bits set", 13, 10

push -1
call CtBits
print str$(eax), " bits set in AX", 13, 10

push 0111011100010100b
call CtBits
print str$(eax), " bits set", 13, 10, 10

print "Counting bits in a macro: ", 13, 10

mov eax, 0
print str$(PopCount(ax)), " bits set", 13, 10

mov eax, -1
print str$(PopCount(ax)), " bits set in AX", 13, 10

mov eax, -1
print str$(PopCount(eax)), " bits set - this is EAX, 32 bits", 13, 10

mov eax, 0111011100010100b
print str$(PopCount(ax)), " bits set", 13, 10, 10

mov ecx, 0
print str$(PopCount(cx)), " bits set", 13, 10

mov ecx, -1
print str$(PopCount(cx)), " bits set in CX", 13, 10

mov ecx, -1
print str$(PopCount(ecx)), " bits set - this is EAX, 32 bits", 13, 10

mov ecx, 0111011100010100b
print str$(PopCount(cx)), " bits set", 13, 10

getkey
exit

CtBits proc uses ecx edx arg
mov edx, arg
xor eax, eax
mov ecx, 16 ; 16 bits only - put 32 if needed
@@: rol dx, 1
adc eax, 0
dec ecx
jne @B
  ret
CtBits endp
end start


[dedndave]

here's another twist on Jochen's/Japheth's code

CtBits  proc uses bx dx arg

        mov     dx,arg
        xor     ax,ax
        mov     bx,ax

@@:     shr     dx,1
        jz      @F

        adc     ax,bx
        jmp     @B

@@:     adc     ax,bx
        ret

CtBits  endp

even faster is not to use a stack frame - also - eliminate the jmp...

        mov     dx,TestVal
        call    CBits

;bit count is in AX - bit 0 will tell you if odd/even parity
.
.
CBits   PROC

        push    bx
        xor     ax,ax       ;XOR always clears the carry flag
        push    dx
        mov     bx,ax

CBits0: adc     ax,bx
        shr     dx,1        ;the zero flag is set if DX = 0
        jnz     CBits0      ;JNZ does not look at the carry flag

        pop     dx
        adc     ax,bx       ;don't forget the last carry bit
        pop     bx
        ret

CBits   ENDP

[FORTRANS]

Hi Veronica,

  I don't have your library, so take this with a grain of salt.  When you
call GETDEC$ where is your number stored?  If it is in AX it may be
destroyed when you call other routines.  You should ensure that
it is used by PUTBIN as expected.  If it ends up in NUMBER, and that
is used properly by PUTBIN, then:

Code Select Expand


       MOV     AX,[NUMBER]
       CALL    PARITY


and don't POP AX (or push it later) _should_ make your code work.
Pushing and popping stuff should be done with care, check in
DEBUG the first time around if necessary.

  Look at the other suggestions to see what else you can do.
They are interesting, and do show better ways to do things, but
your code should work with the few fixes, unless I've missed
something as usual.  If you want to do more than one number,
don't forget to zero ONES_COUNT when you enter PARITY.

HTH,

Steve N.

[ilian007]

Veronica what I did is right before calling parity subprocedure in main I moved ax to cx : MOV CX,AX then in parity.asm I dit: MOV AX,CX and everything works. sure u should have USES AX CX .. etc in parity.asm

[dedndave]

        mov     dx,TestVal
        call    CBits

;ax = bit count - bit 0 will tell you if odd/even parity
;dx = TestVal
.
.
CBits   PROC

        push    bx
        xor     ax,ax       ;XOR always clears the carry flag
        push    dx
        mov     bx,ax

CBits0: adc     ax,bx
        shr     dx,1        ;the zero flag is set if DX = 0
        jnz     CBits0      ;JNZ does not look at the carry flag

        pop     dx
        adc     ax,bx       ;don't forget the last carry bit
        pop     bx
        ret

CBits   ENDP

[veronicak5678]

Thanks to everyone for answering. I wanted to stick with my original method, really just because I understood it, but the pops and pushes were screwing it up. My teacher made it seem like the thing to do, but I guess it's not so simple.

Here's what I ended up with:

Code Select Expand

;===================================================================
;                   MAIN.ASM
;===================================================================
         EXTERN  GETDEC$:FAR
         EXTERN  NEWLINE:FAR
         EXTERN  PUTSTRNG:FAR
         EXTERN  PUTDEC$:FAR
         EXTERN  PUTBIN:FAR
         EXTERN  PARITY:FAR
;===================================================================
        .MODEL  LARGE
        .STACK  512
;===================================================================
; D A T A   S E G M E N T   D E F I N I T I O N
        .DATA
NUMBER      DW  ?
PROMPT DB  'Enter a number: '
BINDISPLAY    DB  'Number in binary: '
ONESDISPLAY     DB  'Number of 1s: '
ODDDISPLAY      DB  'The number of 1s is odd. '
EVENDISPLAY     DB  'The number of 1s is even. '
NUMDISPLAY     DB  'The number IS '
;===================================================================
; C O D E   S E G M E N T   D E F I N I T I O N
        .CODE
        ASSUME  DS:DGROUP
;===================================================================

MAIN    PROC

        MOV     AX,DGROUP           ;SET DS-REGISTER TO POINT TO
        MOV     DS,AX               ;DATA SEGMENT
        MOV     ES,AX               ;AND ES ALSO

        CALL    NEWLINE
        MOV     DI, OFFSET PROMPT
        MOV     CX, SIZEOF PROMPT
        CALL    PUTSTRNG
        CALL    GETDEC$
MOV NUMBER, AX
        CALL    NEWLINE
        MOV     DI, OFFSET BINDISPLAY
        MOV     CX, SIZEOF BINDISPLAY
        CALL    PUTSTRNG
MOV BL, 1
CALL    PUTBIN






        MOV AX, NUMBER
        CALL    PARITY
CALL    NEWLINE
        CALL    NEWLINE
        MOV     DI, OFFSET ONESDISPLAY
        MOV     CX, SIZEOF ONESDISPLAY
        CALL    PUTSTRNG
        CALL    PUTDEC$
        CALL    NEWLINE 
SUB     DX, DX
        MOV     BX, 2
        DIV     BX
        CMP     DX, 0
        JNE     ODDS
        MOV     DI, OFFSET EVENDISPLAY
        MOV     CX, SIZEOF EVENDISPLAY
        CALL    NEWLINE
        CALL    PUTSTRNG
        CALL    NEWLINE
CALL    NEWLINE
        JMP     EXIT_PROGRAM
ODDS:   
        MOV     DI, OFFSET ODDDISPLAY
        MOV     CX, SIZEOF ODDDISPLAY
        CALL    NEWLINE
        CALL    PUTSTRNG 
CALL    NEWLINE
        CALL    NEWLINE     
EXIT_PROGRAM:
.EXIT
        MOV     AX, 4C00H
        INT     21H
MAIN    ENDP
        END MAIN

Code Select Expand

;;===================================================================
;              Veronica Kaufman
;                 CISP 310
;                PARITY.ASM
;===================================================================
         .MODEL  LARGE     
;===================================================================
; D A T A   S E G M E N T   D E F I N I T I O N
        .DATA
ONES_COUNT     DW      0                           
;===================================================================
; C O D E   S E G M E N T   D E F I N I T I O N
        .CODE   
        ASSUME  DS:DGROUP
;===================================================================

PARITY  PROC    FAR PUBLIC USES CX DX DS
MOV ONES_COUNT, 0
NUM_LOOP:
CMP AX, 0
JE  END_PROGRAM
SHL AX, 1
JC  INCREMENT
JMP NUM_LOOP
INCREMENT:
INC ONES_COUNT
JMP NUM_LOOP
END_PROGRAM:
MOV AX, ONES_COUNT
RET
PARITY  ENDP
        END PARITY

[dedndave]

that's ok, Veronica
your prof would know the above routine was not written by a student - lol
it is the result of 3 fairly experienced asm programmers bumping ideas together

[FORTRANS]

Hi Dave,

   Doing any timing tests?

Code Select Expand


; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; 0 = 1, 1 = 8, 2 = 28, 3 = 56, 4 = 70, 5 = 56, 6 = 28, 7 = 8, 8 = 1
CntTable DB     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
        DB      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
        DB      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
        DB      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
        DB      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6
        DB      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
        DB      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7
        DB      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
; Counts bits set in AX.  Returns count of bits in AX, original
; AX destroyed.
PARITY  PROC
        MOV BX, OFFSET CntTable
        XLATB
        XCHG    AL,AH
        XLATB
        ADD     AL,AH
        XOR     AH,AH
        RET
PARITY  ENDP


Cheers,

Steve N.