Определить знак 32-битного int

Question

Использование ТОЛЬКО:

! ~ & ^ | + << >>

NO LOOPS

Мне нужно определить знак 32-битного целого числа, и мне нужно вернуть 1, если положительный, 0, если 0, и -1, если отрицательный.

Есть идеи? Сначала я подумал о переключении на 31 бит, а затем посмотрел на этот знак, но это, очевидно, не сработало, и теперь я застрял.

Answer 1

Если допустимы условные выражения (не if) и вычитание, самое простое и чистое решение (IMO):

int sign = (v > 0) - (v < 0);

Не использовать вычитание (и предполагается, что int составляет 32 бита)

#include <stdio.h>
#include <assert.h>
#include <limits.h>

int process(int v) {
    int is_negative = (unsigned int)v >> 31; // or sizeof(int) * CHAR_BIT - 1
    int is_zero = !v;
    int is_positive = !is_negative & !is_zero;
    int sign = (is_positive + ~is_negative) + 1;
    return sign;
}

int main() {
    assert(process(0) == 0);
    printf("passed the zero test\n");
    for (int v = INT_MIN; v < 0; v++) {
        assert(process(v) == -1);
    }
    printf("passed all negative tests\n");
    for (int v = 1; v < INT_MAX; v++) {
        assert(process(v) == +1);
    }
    printf("passed all positive tests\n");
    return 0;
}

Вот результаты:

$ gcc -o test test.c -Wall -Wextra -O3 -std=c99 && ./test && echo $#
passed zero test
passed all negative tests
passed all positive tests
0

Answer 2

Попробуйте:

(x >> 31) | (((0 - x) >> 31) & 1)

Как насчет этого:

(x >> 31) | (((~x + 1) >> 31) & 1)

РЕДАКТИРОВАТЬ 2:

В ответ на вопросы (или, скорее, придирки), возникшие вкомментарии ...

Допущения для правильности этих решений:

1. x имеет тип 32-разрядное целое число со знаком.
2. В этой системе подписано 32-битные целые числа являются дополнением до двух.(сдвиг вправо арифметический)
3. Обтекание при арифметическом переполнении.
4. Для первого решения литерал 0 того же типа, что и x.

Answer 3

Немного более запутанно, но есть это:

(~((x >> 31) & 1) + 1) | (((~x + 1) >> 31) & 1)

Это должно позаботиться о неоднозначности того, заполнит ли сдвиг 1 или 0

Для разбивки, в любом месте у нас есть эта конструкция:

(z >> 31) & 1

Результатом будет 1, если отрицательно, и 0 в противном случае.

В любом месте у нас есть:

(~z + 1)

Получаем отрицательное число (-z)

Таким образом, первая половина выдаст результат 0xFFFFFFFF (-1), если x будет отрицательным, а вторая половина выдаст 0x00000001 (1), если x будет положительным. Побитовое или объединение их вместе приведет к получению 0x00000000 (0), если ни один из них не равен true.

Answer 4

Зачем вам для этого нужно использовать побитовые операторы?

int get_sign(int value)
{
    return (value < 0) ? -1 : (int)(value != 0);
}

Если вам абсолютно необходимо использовать побитовые операторы, то вы можете использовать оператор & для проверки на отрицательные значения, сдвиг не требуется:

int get_sign(int value)
{
    return (value & 0x80000000) ? -1 : (int)(value != 0);
}

Если вы хотите сдвинуть:

int get_sign(int value)
{
    return ((value >> 31) & 1) ? -1 : (int)(value != 0);
}

Answer 5

Я не уверен, что это абсолютно идеальный способ сделать что-то, но я думаю, что он достаточно переносим и, по крайней мере, несколько проще, чем у вас:

#define INT_BITS 32

int sign(int v) { 
    return (!!v) | -(int)((unsigned int)v >> (INT_BITS-1));
}

Answer 6

Предполагая, что реализация определяет арифметическое смещение вправо:

(x>>31) | !!x

В отличие от ответа Mystical, UB отсутствует.

И, если вы хотите также поддерживать системы, в которых сдвиг вправо определен как арифметический сдвиг:

~!(x>>31)+1 | !!x

Редактировать: Извините, я опустил ! во второй версии. Должно быть:

~!!(x>>31)+1 | !!x

Эта версия по-прежнему зависит от реализации, дополняемой двумя и имеющей либо арифметику или логическое смещение вправо, т. Е. Если бы поведение, определяемое реализацией, было чем-то другим, оно могло бы нарушиться , Однако если вы измените типы на unsigned types, все поведение, определяемое реализацией, исчезнет, ​​и в результате вы получите -1U, 0U или 1U в зависимости от знака (старший бит) и нулевой / ненулевой статус) x.

Answer 7

А как же:

int getsign(int n)
{
  return (!!n) + (~((n >> 30) & 2) + 1);
}

.. для 32-разрядного со знаком int, только с дополнением 2.

!!n дает 1, если n отлично от нуля. ((n >> 30) & 2) дает 2, если установлен старший бит (знак). Побитовое НЕ и +1 берут 2-е дополнение этого, давая -2 или 0. Добавление дает -1 (1 + -2) для отрицательных значений, 0 (0 + 0) для нуля и +1 (1 + 0) для положительных значений.

Answer 8

Идею Дмитрия можно упростить до (!! x) - ((x >> 30) & 2)

И просто дать еще одно загадочное решение:

~!x & ((-((unsigned) x >> 31)) | !!x)