CODEWITHSUNDEEP
assemblyx86nasm
Saumya Sahay
Saumya Sahay

Reputation: 63

x86: Count transitions from 1 to 0 in 32 bit number

I like to count the number of 1 to 0 transition in a 32 bit number. I found that the number of transitions from 0 to 1 in reverse order using shr, but I don't get the required result. What should I do?

extern printf                   
SECTION .data                   
    msg:      db "The number of transitions are : %d",10,0  
    inta1:    dd 1234567   ; integer 1234567        
    num:      dd 4660  
SECTION .text                    

global main               
main:     
    mov eax, [num]    
    mov ecx,32    
    mov ebx,0    
.loop:  dec ecx  
    cmp ecx,0  
    jl .exit   
    shr eax,1  
    jc .loop  
    dec ecx  
    shr eax, 1  
    jnc .loop  
    inc ebx  
    jmp .loop  
.exit:  
    push ebx  
    push    dword msg          
    call    printf             
    add     esp, 8

Output:

The number of transitions are : 2

whereas for 4660 (00000000000000000001001000110100) the number of 1 to 0 transitions are 4.

Upvotes: 2

Views: 371

Answers (2)

Chris Dodd
Chris Dodd

Reputation: 126223

The basic problem is that your code looks for a 0 followed by a 1 and if it doesn't match, it starts over again. So if it sees 00 it starts over looking for another 0 and if the next bit is 1 it starts over. So you miss transitions when they are preceeded by an even number of 0s

Note also you say you want 1-to-0 transitions, but you're looking for 0-to-1 transitions, BUT you are looking right to left (lsb to msb) so that may be correct, depending on which bit order you want.

The obvious solution is to change the jnc .loop to not start over, but only go back to the immediately preceeding dec ecx, though you also need a cmp ecx,0; jl .exit there.

Note also you could get rid of the need of ecx and counting the number of bits by using the Z flag which is set by the shr instruction when the result (in eax) is all 0 bits.

Taken together, that gives you something like:

.loop1: shr eax, 1
        jc .loop1
.loop2: jz .exit
        shr eax, 1
        jnc .loop2
        inc ebx
        jmp .loop1

Upvotes: 4

zx485
zx485

Reputation: 29022

Trivia: I thought about this some month ago while trying to implement an aspect of a bitmap based memory manager.

The most efficient solution I found is the following (I adapted it to your sample code):

global main               
main:     
    mov eax, [num]    
    ; --- here starts the relevant code ---
    mov ebx, eax         
    shl ebx, 1
    not eax
    and ebx, eax
    popcnt ebx, ebx     ; --- count the changed bits ---
    ; --- continue with your exit routine
.exit:  
    push ebx  
    push    dword msg          
    call    printf             
    add     esp, 8

Notice that the calculation is achieved without loops. It is pure bit-fiddling with the set bits being counted at last by the POPCNT instruction giving the desired result.

As an example - applied to the given value of 4660 this algorithm functions like this:

00000000000000000001001000110100 --- MOV EBX, EAX

00000000000000000010010001101000 --- SHL EBX, 1
11111111111111111110110111001011 --- NOT EAX
00000000000000000010010001001000 --- AND EBX, EAX => 'and' the last two lines
=> POPCNT (count the bits of the last line) to get the result of 1 to 0 transitions.

Upvotes: 4

Related Questions