Можно ли проверить, является ли число четным или равным 1, используя только побитовые операторы?

Question

Можно ли достичь с помощью только побитовых операторов, ie без логических / сравнительных / отношений операторов?

Это будет по существу эквивалентно следующему.

(a & 1 == 0) || (a == 1)

Я принимаю что во многих языках может потребоваться окончательное сравнение на равенство, чтобы преобразовать результат в значение true / false, но я не рассматриваю это в этом вопросе. Ответ, который принимает массив входных битов и возвращает тот же массив выходных битов для четного числа, что и для «1», по сути, является тем, что я ищу. Либо это, либо причина, по которой это невозможно.

Answer 1

((a & 1) == 0) | (a == 1) работает. Нет необходимости делать какие-либо сложные трюки

Answer 2

Я не совсем уверен, что понимаю, о чем вы спрашиваете, но в наборе команд Intel64 / AMD64 / x86_64 легко выполнить последовательность побитовых операций, которые будут возвращать значение и флаг кода состояния, который позволяет предлагаемое сравнение.

Предположим, что входное значение находится в регистре% rax.

MOV %rax, %r8     # replicate input value into %r8
MOV %rax, %r9     # replicate input value into %r9
AND $0x1, %r8     # AND 0x1 with the contents of %r8 and put result in %r8
XOR $0x1, %r9     # XOR 0x1 with the contents of %r9 and put result in %r9
OR  %r8, %r9      # OR %r8 with %r9 and put result in %r9

Операция AND вернет 0, если вход четный, иначе вернет 1. XOR операция вернет 0, если входное значение равно 0x1, в противном случае возвращается ненулевое значение. Операция ИЛИ вернет 0, если% r8 и% r9 равны нулю, в противном случае она возвращает ненулевое значение.

Каждая из побитовых операций устанавливает различные флаги условий. Соответствующий здесь называется "ZF", который устанавливается в 1, если результат операции равен 0.

Флаг ZF, установленный конечной операцией, может использоваться для управления условной ветвью. Используйте «JZ» (переход, если ноль) для перехода, если ZF = 1 (то есть условие выполнено), или «JNZ» (переход, если не ноль) для перехода, если условие не истинно.

Вы можете сохранить результат из% r9 в памяти и использовать его позже при сравнении с нулем (true) или не с нулем (false).

Вы также можете воздействовать на результат, не используя команду условного перехода - тот же код условия можно использовать для управления командой условного перемещения. Инструкция CMOVE скопирует входной операнд в памяти или в регистр в выходной регистр, если ZF = 1, или CMOVNE выполнит копирование, если ZF = 0. Например, вы можете скопировать значение «1» из исходного регистра в регистр назначения, если условие выполнено, а затем накопить значения регистра назначения в накопителе. В этом случае аккумулятор будет содержать количество случаев, для которых сравнение вернуло «True».

Answer 3

Хотя я бы не советовал делать это вообще, но я смог добиться этого за C, но только сделав a равным unsigned char. Это может работать и с другими, но это удлинит условие.

#include <stdio.h>

int main() {
    for (unsigned char a = 0; a < 255; a++) {
        if ((~a & 1) | (1 >> (a & 0x0E | a >> 4)))
            printf ("%d is even or 1\n", a);
        else
            printf("%d is odd\n", a);
    }
    return 0;
}

(~a & 1) даст 1, если a четное. (a & 0x0E | a >> 4) даст 0, когда a будет 1 или 0. Поэтому в этих случаях (1 >> (a & 0x0E | a >> 4))) будет (1 >> 0), то есть 1, в противном случае значение сдвига будет между 1 и 15, поэтому я сделал выражение 0.

Мой первоначальный подход был (1 >> (a >> 1)), но вскоре понял, что это вызывает переполнение сдвига, поскольку величина сдвига превышает максимально возможную. И не просто выдавать это предупреждение, а фактически ложно распознавать все n * 64 + 1 значения как четные. Таким образом, более сложный подход заключается в том, чтобы ограничить величину сдвига менее чем 64, ИЛИ -ing a старший 4 бит с его младшим 4 битом, но с установкой LSB в 0. Это результирующее число равно <= 15 и 0, только когда a равно 1 или 0 так, как необходимо.

Answer 4

Метод, который работает для любой фиксированной (степени двойки) ширины битов, заключается в использовании следующей функции, которая возвращает 1, когда все биты установлены, и 0 в противном случае:

uint32_t allOnes(uint32_t a) {
    a &= a >> 1;
    a &= a >> 2;
    a &= a >> 4;
    a &= a >> 8;
    a &= a >> 16;
    return a;
}

Затем мы можем сделать проверка следующим образом:

uint32_t f1(uint32_t a) {
    return (~a & 1) | allOnes(a ^ ~uint32_t(1));
}