Проверьте, не является ли число ненулевым, используя побитовые операторы в C

Question

Проверьте, является ли число x ненулевым, используя законные операторы, кроме !.

Примеры: isNonZero(3) = 1, isNonZero(0) = 0

Юридические операции: ~ & ^ | + << >>

• Примечание: следует использовать только побитовые операторы.if, else, for и т. Д. Использовать нельзя.
• Edit1: число операторов не должно превышать 10.
• Edit2: Учитывать размер int для4 байта.

int isNonZero(int x) {
return ???;
}

Использование ! было бы тривиально, но как мы можем это сделать без использования !?

Answer 1

Логарифмическая версия функции adamk:

int isNotZero(unsigned int n){
  n |= n >> 16;
  n |= n >> 8;
  n |= n >> 4;
  n |= n >> 2;
  n |= n >> 1;
  return n & 1;
};

И самая быстрая, но в сборке:

xor eax, eax
sub eax, n  // carry would be set if the number was not 0
xor eax, eax
adc eax, 0  // eax was 0, and if we had carry, it will became 1

Что-то похожее на версию сборки можно написать на C, выпросто надо поиграть со знаковым битом и с некоторыми отличиями.

РЕДАКТИРОВАТЬ: вот самая быстрая версия, которую я могу придумать в C:

1) для отрицательных чисел: если знаковый битустановить, число не равно 0.

2) для положительного: 0 - n будет отрицательным, и может быть проверено, как в случае 1. Я не вижу - в списке юридическихоперации, поэтому мы будем использовать ~n + 1 вместо.

Что мы получаем:

int isNotZero(unsigned int n){ // unsigned is safer for bit operations
   return ((n | (~n + 1)) >> 31) & 1;
}

Answer 2

int isNonZero(unsigned x) {
    return ~( ~x & ( x + ~0 ) ) >> 31;
}

Предполагая, что int равен 32 битам (/ * EDIT: эта часть больше не применяется, поскольку я изменил тип параметра на unsigned * / и что сдвиги со знаком ведут себя точно так же, как и беззнаковые).

Answer 3

Почему все усложняется?

int isNonZero(int x) {
    return x;
}

Это работает, потому что соглашение C гласит, что каждое ненулевое значение означает истину, поскольку isNonZero возвращает допустимое int.

Некоторые люди утверждали,функция isNonZero () должна возвращать 1 для входа 3, как показано в примере.

Если вы используете C ++, все так же просто, как и раньше:

int isNonZero(int x) {
    return (bool)x;
}

Теперь функция возвращает 1, есливы предоставляете 3.

ОК, он не работает с C, который пропускает правильный логический тип.

Теперь, если вы предполагаете, что целые числа 32-битные и допускается +:

int isNonZero(int x) {
    return ((x|(x+0x7FFFFFFF))>>31)&1;
}

На некоторых архитектурах вы можете даже избежать финального &1, просто приведя x к unsigned (который имеет нулевую стоимость времени выполнения), но это Undefined Behavior, следовательно, зависит от реализации (зависит, если целевая архитектура использует подписанный илилогический сдвиг вправо).

int isNonZero(int x) {
    return ((unsigned)(x|(x+0x7FFFFFFF)))>>31;
}

Answer 4

int is_32bit_zero( int x ) {
    return 1 ^ (unsigned) ( x + ~0 & ~x ) >> 31;
}

1. Вычесть 1. (~0 генерирует минус один на машине дополнения до двух. Это предположение.)
2. Выберите только перевернутый бит, который перевернулся на единицу.
3. Наиболее значимый бит переворачивается только в результате вычитания единицы, если x равен нулю.
4. Перемещение старшего значащего бита в младший значащий бит.

Я считаю шесть операторов. Я мог бы использовать 0xFFFFFFFF для пяти. Приведение к unsigned не рассчитано на машину для дополнения до двух; v).

http://ideone.com/Omobw

Answer 5

Побитовое ИЛИ все биты в числе:

int isByteNonZero(int x) {
    return ((x >> 7) & 1) |
           ((x >> 6) & 1) |
           ((x >> 5) & 1) |
           ((x >> 4) & 1) |
           ((x >> 3) & 1) |
           ((x >> 2) & 1) |
           ((x >> 1) & 1) |
           ((x >> 0) & 1);
}

int isNonZero(int x) {
  return isByteNonZero( x >> 24 & 0xff ) |
         isByteNonZero( x >> 16 & 0xff ) |
         isByteNonZero( x >> 8  & 0xff ) |
         isByteNonZero( x       & 0xff );
}

Answer 6

Мое решение в C. Нет оператора сравнения.Не работает с 0x80000000.

#include <stdio.h>

int is_non_zero(int n) {
    n &= 0x7FFFFFFF;
    n *= 1;
    return n;
}

int main(void) {
    printf("%d\n", is_non_zero(0));
    printf("%d\n", is_non_zero(1));
    printf("%d\n", is_non_zero(-1));
    return 0;
}

Answer 7

Мое решение следующее,

int isNonZero(int n)
{
    return ~(n == 0) + 2;
}

Answer 8

Следующий пример функции должен работать для вас.

bool isNonZero(int x)
{
    return (x | 0);
}

Answer 9

return ((val & 0xFFFFFFFF) == 0? 0: 1);

Answer 10

if(x)
     printf("non zero")
else
     printf("zero")