Проверьте, не является ли число ненулевым, используя побитовые операторы в 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.

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

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

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

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

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

В основном вам нужно или биты. Например, если вы знаете, что ваш номер имеет ширину 8 бит:

int isNonZero(uint8_t x)
{
    int res = 0;
    res |= (x >> 0) & 1;
    res |= (x >> 1) & 1;
    res |= (x >> 2) & 1;
    res |= (x >> 3) & 1;
    res |= (x >> 4) & 1;
    res |= (x >> 5) & 1;
    res |= (x >> 6) & 1;
    res |= (x >> 7) & 1;

    return res;
}

Answer 7

Мое решение в 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 8

Мое решение заключается в следующем,

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

Answer 9

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

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

Answer 10

Мое решение, хотя и не совсем связанное с вашим вопросом

int isSign(int x)

{
//return 1 if positive,0 if zero,-1 if negative
return (x > 0) - ((x & 0x80000000)==0x80000000)
}

Answer 11

Эта функция вернет x если он ненулевой, в противном случае он вернется 0,

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

Answer 12

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

Answer 13

int isNonZero (int x)

{

if (  x & 0xffffffff)
    return 1;
else
    return 0;

}

Предположим, что Int 4 байта.

Он вернет 1, если значение не ноль

если значение равно нулю, он вернет 0.

Answer 14

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