Как найти TMax без использования смен

Question

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

 ! ~ & ^ | +

Как я могу узнать, является ли 32-битное число TMax?

TMax - это максимальное число дополнений до двух.

До сих пор мои мысли были:

int isTMax(int x)
{
  int y = 0;

  x = ~x;
  y = x + x;

  return !y;
}

Это всего лишь одна из многих вещей, которые я безуспешно пробовал, но я просто не могу вспомнить свойство TMax, которое вернуло бы мне TMax. Как добавление tmax к себе будет уникальным по сравнению со всеми другими целыми числами.

---

Вот актуальная проблема:

/*
 * isTMax - return 1 if x is the maximum, two's complement number,
 *     and 0 return otherwise. 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTMax(int x) {
        int y = 0;

  x = ~x;
  y = x + x;

  return !y;
}

int - это 32 бита, поэтому максимальное значение со знаком, вероятно, будет 0x7FFFFFFF

Answer 1

Насколько я знаю, нет способа определить, является ли конкретное значение максимальным значением типа со знаком , не зная уже максимального значения этого типа и не проводя прямого сравнения. Это потому, что подписанные выражения испытывают неопределенное поведение при переполнении. Если бы был ответ на ваш вопрос, это означало бы существование ответа на серьезную нерешенную проблему, которая некоторое время обсуждалась в SO: как программно определить максимальное значение для данного типа со знаком.

Answer 2

int isTmax(int x) {


    //add one to x if this is Tmax. If this is Tmax, then this number will become Tmin
    //uses Tmin = Tmax + 1
    int plusOne = x + 1;

    //add to x so desired input becomes 0xFFFFFFFF, which is Umax and also -1
    //uses Umax = 2Tmax + 1
    x = x + plusOne;

    plusOne = !(plusOne);

    //is x is 0xffffffff, then this becomes zero when ~ is used
    x = ~x;
    x = x | plusOne;
    x = !x;

    return x;
}

Answer 3

Потратьте 3 часа на эту проблему. Я знаю, что эта проблема исходит из лаборатории данных csapp, и ее новейшее требование -

1. Integer constants 0 through 255 (0xFF), inclusive. You are
  not allowed to use big constants such as 0xffffffff
....

* isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1

Итак, оператор сдвига (<< / >> и 0x7FFFFFFF из принятого ответа теперь запрещен)

Ниже мой путь:

TDD-стиль:

isTmax(2147483647) == isTmax(0b011111111111...1) == 1
isTmax(2147483646) == isTmax(0b011111111111...0) == 0
isTmax(-1) == isTmax(0b111111111...1) == 0
isTmax(-2147483648) == isTmax(0b100000000...0) == 0 

возврат должен быть либо 0, либо 1. In, c, ! + все ненулевые значения вернут 0. Так что ! является обязательным, в противном случае мы не можем гарантировать получение 0 для всех номеров.

Первая наивная попытка:

потому что 0b0111111...1 (он же 2147483647) является единственным аргументом, который должен сделать isTmax return 1, а 2147483647 + 1 должно быть 10000000...0 (он же -2147483648)

0b011111111...1 xor 0b1000000000...0 - это 0b11111111111...111. Поскольку мы должны использовать !, мы надеемся увидеть 0 (он же 0b0000000000000...0). Очевидно, просто примените логика, а не (он же !) к 0b1111111...1), тогда мы получим 0b000000000000):

!(~(x ^ (x + 1))

давайте распечатаем это

void print(int x)
{
     printf("%d\n", !(~(x ^ (x + 1))));
}
int main() {
        print (2147483647);
        print(2147483646);
        print(-1);
        print(-2147483648);
}

* * 1 тысяча сорок-девять

0

1

0

live demo

Неплохо, только -1 работает не так, как мы ожидали.

вторая попытка:

Давайте сравним -1 и 2147483647

11111111111111111111111111111111
01111111111111111111111111111111

Мы можем найти -1 + 1 = 0, а 2147483647 + 1 = -2147483648. Еще раз подчеркнем, что нам нужны diff -1 и 2147483647, потому что они оба возвращают 1, как показано выше. Посмотрите назад на защиту логики , а не в c: все ненулевые вернут 0 , поэтому !-2147483648 == 0 и !(-1 + 1) != 0. Просто измените левую часть x ^ (x + 1) (x) на x + !(x + 1). Если х равен 2147483647, x + !(x + 1) будет равен x.

Запустить снова:

void print(int x)
{
    printf("%d\n", !(~( x + !(x + 1) ^ (x + 1))));
}
int main() {
        print (2147483647);
        print(2147483646);
        print(-1);
        print(-2147483648);
}

1

0

0

0

live demo

Готово!

Answer 4

, если это Tmax: 011111 .....

, тогда мы хорируем его с 10000 ....

, мы получаем 11111 ....

тогдамы ~ чтобы получить все 0s = 0,! 0 мы получаем 1:

int isTmax(int x) {
  return !(~((1 << 31) ^ x ));
}

Answer 5

#include <stdio.h>
#include <stdlib.h>

int test(int n) {
  return !(n & 0x80000000) & !~(n | (n + 1));
}

// or just effectively do a comparison

int test2(int n) {
  return !(n ^ 0x7fffffff);
}

int main(int ac, char **av) {
  printf("is%s TMax\n", test(atoi(av[1])) ? "" : " not");
  return 0;
}

Answer 6

Что-то вроде этого возможно? 0x7FFFFFFF - максимальный 32-битный номер дополнения с положительным знаком.

int isTMax(int x){
    return !(x ^ 0x7FFFFFFF);
}

Я не уверен, вам может понадобиться привести его к unsigned, чтобы он заработал.