优化的可被整除

Question

假设我有数字 X，我想看看它是否可以被 Y 整除。最优化的方法是什么？

到目前为止，我有：

int X = 12;
int Y = 4;
(X ^ Y) & 0b111 ==0    # Check if X XOR Y (mask size Y) == 0

虽然我是硬编码0b111（Y 的掩码大小）。顺便说一句，我不关心语言，我只是用 C 标记它。

---

顺便说一句，使用编译器资源管理器我得到：

int is_divisible_by(int x, int y) {
    return x % y == 0;
};

# -O3
is_divisible_by:
        movl    %edi, %eax
        cltd
        idivl   %esi         # seems to just be doing straight division?
        xorl    %eax, %eax
        testl   %edx, %edx
        sete    %al
        ret

Answer 1

编译器将根据参数使用不同的算法。如果某些是常量表达式或者可以在调用之前预测，它将使用更快的方式来执行它。

int is_divisible_by(const int x, const int y) {
    return !(x % y);
};

int case1(void)
{
    return is_divisible_by(6,3);
}

int case2(int x)
{
    return is_divisible_by(x,2);
}

int case3(int x)
{
    return is_divisible_by(x,5);
}

int case4(int x)
{
    return is_divisible_by(x,255);
}

int case5(int x)
{
    return is_divisible_by(x,32);
}


int case6(int x, int y)
{
    return is_divisible_by(x,y);
}

is_divisible_by:
        mov     eax, edi
        cdq
        idiv    esi
        xor     eax, eax
        test    edx, edx
        sete    al
        ret
case1:
        mov     eax, 1
        ret
case2:
        mov     eax, edi
        not     eax
        and     eax, 1
        ret
case3:
        imul    edi, edi, -858993459
        xor     eax, eax
        add     edi, 429496729
        cmp     edi, 858993458
        setbe   al
        ret
case4:
        imul    edi, edi, -16843009
        xor     eax, eax
        add     edi, 8421504
        cmp     edi, 16843008
        setbe   al
        ret
case5:
        xor     eax, eax
        and     edi, 31
        sete    al
        ret
case6:
        mov     eax, edi
        cdq
        idiv    esi
        xor     eax, eax
        test    edx, edx
        sete    al
        ret

https://godbolt.org/z/9cxEfe