# Shifting bits in assembly (nasm)

I wrote a function which takes a byte and shifts the bits around. That is, there shall be the same number of 1 bits and 0 bits in the output but the bits will be shifted in position:

global _main
default rel

section .text

_main:
; Given 1 byte, shift the positions of the bits in the form 74652103
mov bl, 0x5A
; 0101 1010

shift_bits:
; 1. bit 7 stays same
; 2. bit 4 (0x10) gets shifted left by 2 - and with 0001 0000, shift left by 2, or with result
; 3. bit 6 (0x40) gets shifted right by 1
; 4. bit 5 (0x20) gets shifted right by 1
; 5. bit 2 (0x4) gets shifted left by 1
; 6. bit 1 (0x2) gets shifted left by 1
; 7. bit 0 (0x1) gets shifted left by 1
; 8. bit 3 (0x8) gets shifted right by 3
; begin 0101 1010
; expect: 0110 0101
; end 0110 0101
mov al, bl
mov cl, 0
and al, 0x80
or cl, al
mov al, bl
and al, 0x10
shl al, 2
or cl, al
mov al, bl
and al, 0x4
shl al, 1
or cl, al
mov al, bl
and al, 0x2
shl al, 1
or cl, al
mov al, bl
and al, 0x1
shl al, 1
or cl, al
mov al, bl
and al, 0x8
shr al, 3
or cl, al
mov al, bl
and al, 0x2
shl al, 1
mov al, bl
and al, 0x40
shr al, 1
or cl, al
mov byte [A], cl ; Store result in A

go_out:
mov     rax, 0x2000001 ; exit - macOS specific!
mov     rdi, 0
syscall

section .data
A: db 0


Is there a more efficient way to do this with fewer instructions or more performant ones?

• as long as only 8 bit values are involved, you can also use look-up-table (LUT) with size 256B, then the conversion is basically single mov from memory, but I guess you are for some reason trying to avoid this (kinda "cheat", but often used in 8b/16b CPU emulators, etc.. to make the processing speed predictable across different types of calculations and also the LUTs are often 10..20 bits to account not only for the source 8b value, but also the "flag" register and calculating in single mov results of both together). Dec 13, 2019 at 14:07
• and about actually doing the calculation with instructions, which instructions you are willing to accept? The example seems to be x86_64, so you would accept also shrx and similar? (didn't really try, but I would guess it may be favourable for certain intermediate steps, not affecting flags and specifying both source + destination registers saving a copy instruction). Dec 13, 2019 at 14:12

The operation count can be reduced, by using that some bits are moved by the same distance. Bits 0, 1 and 2 can be shifted left in one go. 5 and 6 can be shifted right in one go.

Some shift/bitwise-OR combinations can be written as lea, that would be bad for Pentium 4 but very good on Ryzen and Ice Lake and fine on Haswell/Skylake. Since this is 64bit code it is best to use lea with a 64bit address and then implicitly discard the top half of the result by writing it to a 32bit destination, explicitly using a 32bit address would generate a useless address size override prefix.

The 8 bit operations have a disadvantage on several CPUs that limits their efficiency, they're usually not inherently slow per-se but the problem is that writing to the "low" 8 bit register may have a dependency on the whole register (the "high" registers are an other story and have their own issues), something like mov al, bl doesn't "decouple" the new al from the old al on such CPUs because the write is merged into rax. So unless there is a good reason for writing to an 8 bit register, I would recommend avoiding it, to avoid such odd edge cases of the microarchitecture.

Here is a possible implementation:

    ; keep bit 7 at bit 7
mov     eax, ebx
and     eax, 128
; shift bits 0, 1, 2 left by 1 and combine
mov     ecx, ebx
and     ecx, 7
lea     eax, [rax + 2*rcx]
; shift bit 4 left by 2 and combine
mov     ecx, ebx
and     ecx, 0x10
lea     eax, [rax + 4*rcx]
; shift bit 3 right by 3 and combine
mov     ecx, ebx
and     ecx, 8
shr     ecx, 3
or      eax, ecx
; shift bits 5 and 6 right by 1 and combine
shr     ebx
and     ebx, 0x30
or      eax, ebx
; store result
mov [A], al