Szybsze modulowanie przez 2

Question

Mam pytanie: Czy da się szybciej modulować przez takie liczby jak: 2,4,8,16,32...? Bo przecież dla komputera to jak return'owanie końcówki liczby. Jeśli się da to jaka jest na to komenda.

Answer 1

Jeśli wartość modulo znasz z góry, to nic nie musisz robić - kompilator sam za Ciebie wykona taką optymalizację:

https://godbolt.org/z/xoETna

unsigned int modulo32(unsigned int num) {
    return num % 32;
}

modulo32(unsigned int):
        mov     eax, edi
        and     eax, 31
        ret

 

Answer 2

Faster division and modulo operation - the power of two

Performance wise, how fast are Bitwise Operators vs. Normal Modulus?

Answer 3

v &= (16 - 1);

Answer 4

Żeby coś się dzieliło przez 2 ostatni bit musi być równy 0, aby przez 4 dwa ostatnie muszą być 0, przez 8 trzy ostatnie itd.

Tak jak napisał j23 można to zrobić w następujący sposób, sprawdźmy czy v dzieli się przez 16. 16 - 1 da w miejsca zer jedynki i jak teraz się zrobi and'a z liczbą to wyjdzie zero tylko wtedy gdy cztery ostatnie cyfry tej liczby to zera.