Бит-трюк, чтобы определить, имеет ли какое-либо из целых чисел определенное значение

Ответ 1

Единственное, что я нашел, это:

int s1 = ((a-d) >> 31) | ((d-a) >> 31);
int s2 = ((b-d) >> 31) | ((d-b) >> 31);
int s3 = ((c-d) >> 31) | ((d-c) >> 31);

int s = s1 & s2 & s3;
return (s & 1) == 0;

альтернативный вариант:

int s1 = (a-d) | (d-a);
int s2 = (b-d) | (d-b);
int s3 = (c-d) | (d-c);

int s = (s1 & s2 & s3);
return (s & 0x80000000) == 0;

оба переведены на:

mov     eax, ecx
sub     eax, edi
sub     edi, ecx
or      edi, eax
mov     eax, ecx
sub     eax, esi
sub     esi, ecx
or      esi, eax
and     esi, edi
mov     eax, edx
sub     eax, ecx
sub     ecx, edx
or      ecx, eax
test    esi, ecx
setns   al
ret

который имеет меньше заданных команд, но, очевидно, больше mov/sub.

Обновление: как предлагалось BeeOnRope @- имеет смысл вводить входные переменные в unsigned

Ответ 2

Это не полный трюк. Любой нуль дает нулевое произведение, которое дает нулевой результат. Отрицание 0 дает 1. Не имеет дело с переполнением.

bool test(int a, int b, int c, int d)
{
    return !((a^d)*(b^d)*(c^d));
}

gcc 7.1 -O3. (d находится в ecx, другие входы начинаются в других целочисленных регистрах).

    xor     edi, ecx
    xor     esi, ecx
    xor     edx, ecx
    imul    edi, esi
    imul    edx, edi
    test    edx, edx
    sete    al
    ret

Это может быть быстрее, чем оригинал на Core2 или Nehalem, где проблема частичных регистрационных столов. imul r32,r32 имеет 3c латентность на Core2/Nehalem (и более поздние процессоры Intel) и 1 на пропускную способность каждого тактового сигнала, поэтому эта последовательность имеет 7-секундную задержку от входов до второго результата imul и еще 2 цикла задержки для test/sete. Пропускная способность должна быть достаточно хорошей, если эта последовательность работает на нескольких независимых входах.

Использование 64-битного умножения позволит избежать проблемы переполнения при первом умножении, но второй может все еще переполняться, если сумма равна >= 2**64. Это все равно будет такая же производительность для Intel Nehalem и семейства Sandybridge, и AMD Ryzen. Но это было бы медленнее на более старых процессорах.

В x86 asm выполнение второго умножения с помощью полноразмноженной команды с одним операндом mul (64x64b = > 128b) позволит избежать переполнения, и результат может быть проверен на то, чтобы быть полностью нулевым или нет с помощью or rax,rdx, Мы можем записать это в GNU C для 64-битных целей (где __int128 доступно)

bool test_mulwide(unsigned a, unsigned b, unsigned c, unsigned d)
{
    unsigned __int128 mul1 = (a^d)*(unsigned long long)(b^d);
    return !(mul1*(c^d));
}

и gcc/clang действительно испускают asm, на который мы надеялись (каждый с некоторыми бесполезными инструкциями mov):

   # gcc -O3 for x86-64 SysV ABI
    mov     eax, esi
    xor     edi, ecx
    xor     eax, ecx
    xor     ecx, edx   # zero-extends
    imul    rax, rdi
    mul     rcx        # 64 bit inputs (rax implicit), 128b output in rdx:rax
    mov     rsi, rax   # this is useless
    or      rsi, rdx
    sete    al
    ret

Это должно быть почти так же быстро, как простая версия, которая может переполняться, на современном x86-64. (mul r64 по-прежнему остается только 3 c латентность, но 2 uops вместо 1 для imul r64,r64, который не дает высокую половину), в семействе Intel Sandybridge.)

Это еще хуже, чем clang setcc/or вывод из исходной версии, в котором используются 8-разрядные инструкции or, чтобы избежать чтения 32-разрядных регистров после записи младшего байта (т.е.).

Посмотрите оба источника с обоими компиляторами в проводнике компилятора Godbolt. (Также включена версия @BeeOnRope ^/&, которая подвергает риску ложные срабатывания, с полной отдачей и без нее.)

Ответ 3

return !(a^d && b^d && c^d); может показаться приятным трюком, но не гарантированно будет более эффективным.

Если два целых числа одинаковы, то их xor равно нулю.