How to calculate the sum of a sequence of powers of 2 in x86?

.586 .MODEL FLAT INCLUDE io.h .STACK 4096 .DATA Exponent DWORD ? Prompt BYTE "Enter an exponent", 0 Base DWORD 2 string BYTE 40 DUP (?) resultLbl BYTE "The solution is", 0 Solution DWORD 20 DUP (?), 0 .CODE _MainProc PROC input Prompt, string, 40 ; read ASCII characters (N) atod string ; ascii to double mov exponent, eax ; store in memory push Exponent push Base call function add esp, 8 dtoa Solution, eax ; convert to ASCII characters output resultLbl, Solution ; output label and sum mov eax, 0 ; exit with return code 0 ret _MainProc ENDP ;@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ; Procedure takes base and exponent from main Function PROC push ebp ; stores base pointer mov ebp, esp ; set base pointer to current position mov ebx, [ebp + 12] ; read base (2) mov ecx, [ebp + 8] ; read N MainLoop: ; loop to calculate expoent mul ebx ; multiply base by its self add eax, ebx ; save answer in eax dec ecx ; decrement the exponent cmp ecx, 0 ; check if exponent is 0 yet je exit ; Exit if exponent is 0 jg mainloop ; stay in loop if exponent is above 0 Exit: pop ebp ; restore base pointer ret function ENDP END

Base 2 is an extremely special case because computers use binary integers.

2^n = 1 << n i.e. 2ⁿ = 1 left-shifted n times. i.e. that bit-position is set.

You're asking for 2^0 + 2^1 + ... 2^n. A number with all bits set up to an including bit n.
That's 1 less than 2^(n+1), so the number you want is 2^(n+1) - 1.

x86 has an instruction to set a bit at a given position in a register: bts reg, reg = Bit Test and Set. On Intel CPUs, the reg-reg form decodes to a single uop, with 1-cycle latency. (https://agner.org/optimize/) It also puts the old value of the bit in CF, but normally we don't care about that when using it for this. Normally we just zero a destination register and use BTS to set a single bit.

On Ryzen, bts reg,reg is 2 uops and variable-count shifts are single-uop, so mov edx, 1 / shl edx, cl is good, too. But that's worse for code-size, and more uops on Intel CPUs.

On Intel Sandybridge-family CPUs, shl reg, cl decodes to 3 uops. BMI2 shlx reg, reg, reg is 1 uop, but BMI2 support is still far from being something you can assume, unfortunately.

(Memory-destination BTS with a register source is very slow, treating the source as an indexing into an arbitrary length bit-string, not just the addressed dword, so normally avoid it for performance.)

Calculating `2^(n+1) - 1` without overflow

(C version of this answer on another question, with compiler output.)

If we just added 1 to the input number before feeding it to BTS, it could wrap around and fail to work for 31 (which should set all bits, but would instead set bit 32%32 = 0)

Since we need one extra instruction after reading the input anyway, we can use x86's shift-and-add instruction (LEA) to do one more shift as we subtract 1. So with n=31 we start with the high bit set, and shift it out to get zero. Subtracting 1 then sets all the bits, as desired

xor    edx,edx                 ; edx = 0
bts    edx, eax                ; edx |=  1<<eax
lea    edx, [edx + edx - 1]    ; edx = (edx<<1) - 1

The logic for this goes as follows

n      BTS result (2^n)    *2 - 1
0    ->       1         ->   1        = 2 - 1
1    ->       2         ->   3        = 4 - 1
2    ->       4         ->   7        = 8 - 1
3    ->       8         ->  15        = 16 - 1
...
30   ->  0x40000000     ->  0x7FFFFFFF  = 0x80000000 - 1
31   ->  0x80000000     ->  0xFFFFFFFF  = 0 - 1

It's not a coincidence that the last column is a running total of the 2nd column.

LEA with 3 "components" to the addressing mode has extra latency vs. simpler LEAs, e.g. 3-cycle latency on Sandybridge-family vs. 1 cycle. But it's still a single uop so it's a great choice for throughput.

If we really wanted to optimize, and didn't have to worry about the n=31 case overflowing, we'd write the ASCII -> int loop by hand but start with a total of 1 instead of 0, to fold the n+1 into finding n. Then bts would give us our 2^(n+1), and we could simply dec that.

There's no need to store exponent to memory and reload it again; you already have it in a register where you want it.

Your comment on the atod line is wrong, and your code wouldn't make sense if it was right. ASCII to double (like the C function strtod) would return in x87 st0 or SSE2 xmm0, not EAX. atod actually stands for ASCII (decimal) to integer. Perhaps the d stands for DWORD.

    input   Prompt, string, 40      ; read ASCII characters (N)
    atod    string                 ; ascii (decimal) to integer in EAX

    xor    edx,edx                 ; edx = 0
    bts    edx, eax                ; edx |=  1<<eax
    lea    edx, [edx + edx - 1]    ; edx = (edx<<1) - 1

    dtoa    Solution, edx

It takes 2 instructions to implement 1<<n so it's silly to put it into its own function. Just passing args + calling the function would have take as much work as simply using bts.

0 -> 1 -> 1
1 -> 2 -> 3
2 -> 4 -> 7

Compilers typically use mov edx,1 + mov ecx, eax + shl edx, cl. But that's a missed optimization, especially on Intel CPUs.

BMI2 shlx edx, edx, ecx would help (avoiding the mov), but is worse code-size than xor-zero + bts. And BMI2 isn't always available.

If you can't get your compiler to use BTS (or you have BMI2 for SHLX), another good implementation is (2ULL << n) - 1 so you bake the extra shift into the number you start shifting. So a count of 31 can shift the bit out and produce 0.

Calculating `2^(n+1) - 1` without overflow

Recommended topics

Hot tags

Calculating 2^(n+1) - 1 without overflow

Recommended topics

Hot tags

Calculating `2^(n+1) - 1` without overflow