How to count the number of bits in one byte in assembly language?
Hello.
I can't figure out how to count the number of bits in one byte using the bit mask and the logical operations AND, OR, XOR, NOT.
I write on the 8086 emulator.
What is a bit mask, I know when we can make certain bits of a number zeros or ones, while leaving other bits untouched. But how, using a mask, can you count the number of units in a number consisting of 8 bits (for example, 00011001)?
4 answers
@walik, probably the most obvious algorithm would be:
Установим какой-нибудь регистр в 0xff (т.е. его младший байт будет содержать только единицы) и будем сдвигать его в цикле вправо, пока он не станет нулем. Подсчитаем число итераций и добавим к ним 1.
Now about the assembler. In my opinion, learning from an optimizing compiler is not a bad idea, especially if you know at least a little about C.
Let's write a simple function that implements our algorithm. In order for the compiler not to calculate the answer (yes, if there is enough information, it will do this and deprive us of the assembly code), we will pass it the filled register through the argument functions.
Here is the sishny code of our function:
int nbits (int m) {
int n = 0;
while (m >>= 1)
n++;
return n + 1;
}
Let's call the compiler to get its optimized assembly code: gcc -S -O3 nbits.c
and we get the following text in the nbits.s file:
.file "nbits.c"
.text
.p2align 4,,15
.globl nbits
.type nbits, @function
nbits:
.LFB0:
.cfi_startproc
sarl %edi
je .L5
xorl %eax, %eax
.p2align 4,,10
.p2align 3
.L4:
addl $1, %eax
sarl %edi
jne .L4
addl $1, %eax
ret
.L5:
movl $1, %eax
ret
.cfi_endproc
.LFE0:
.size nbits, .-nbits
.ident "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
.section .note.GNU-stack,"",@progbits
The calling program passes a single argument in the edi register to nbits(). The result we are interested in is returned in the eax register.
Since you are learning assembly language, I think you will find out from there yourself and bring the relevant loop to the desired form.
Caller main obvious:
// file c.c: prints byte size using external function
int
main (int ac, char *av[])
{
return printf ("byte size: %d\n", nbits(0xff)) == EOF;
}
Now let's put it all together and look at the result:
avp@avp-ubu1:hashcode$ gcc c.c nbits.s -O3
avp@avp-ubu1:hashcode$ ./a.out
byte size: 8
avp@avp-ubu1:hashcode$ uname -a
Linux avp-ubu1 3.13.0-39-generic #66-Ubuntu SMP Tue Oct 28 13:30:27 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux
avp@avp-ubu1:hashcode$
If you need to count the bits in a byte, the easiest way is to use a lookup table:
mov ebx, table
xlat
; ...
table db 0 ; 0000 0000
db 1 ; 0000 0001
db 1 ; 0000 0010
db 2 ; 0000 0011
; и т. д.
In short, I didn't really find how to do it, so to meet the conditions of the task (use logical operations and a bit mask), I just went through each bit individually and compared it:
mov cx, 0
mov ax, 00011001b
mov bx, ax ;сохраняем в BX наше число
and bx, 00000001b ;Аннулируем все биты кроме первого
jz label1 ;Если первый бит тоже был нулем, то результатом станет ноль, значит флаг ZF будет равен одному и мы перепрыгнем след. инструкцию, если же бит был единицей, то инкрементируем регистр CX.
inc cx
label1: ;То же самое, только уже со вторым битом
mov bx, ax
and bx, 00000010b
jz label2
inc cx
label2:
mov bx, ax
and bx, 00000100b
jz label3
inc cx
label3:
mov bx, ax
and bx, 00001000b
jz label4
inc cx
label4:
mov bx, ax
and bx, 00010000b
jz label5
inc cx
label5:
mov bx, ax
and bx, 00100000b
jz label6
inc cx
label6:
mov bx, ax
and bx, 01000000b
jz label7
inc cx
label7:
mov bx, ax
and bx, 10000000b
jz label8
inc cx
label8:
The CX register eventually stores a digit that corresponds to the number of units in a byte.
Let's count the number of bits in the al register, and put the result in ecx, then:
xor ecx, ecx
_loop:
shr al, 1
adc ecx, 0
test al, al
jnz _loop
; ecx = количество бит в al
That's all.
Walik, pay attention to the test statement. It acts on the flags in the same way as the and instruction, but it does not write the result of calculations to the receiver register. Therefore, you do not need to "restore" the register value every time, and jz and other conditional transitions will work correctly.
There is another solution, it is unusual and does not use any conditional transitions at all:
; подсчитываем количество бит в регистре al
; результат будет также содержаться в этом же регистре (al)
; регистр cl используем для хранения промежуточных результатов
mov cl, al
and cl, 0x55
shr al, 1
and al, 0x55
add al, cl
;------
mov cl, al
and cl, 0x33
shr al, 2
and al, 0x33
add al, cl
;------
mov cl, al
and cl, 0x0F
shr al, 4
and al, 0x0F
add al, cl
; на данном этапе al = искомое количество бит
The code is correct and does not contain any conditional transitions. Why this works is described in the book "Algorithmic Tricks for Programmers"by Henry Warren Jr.