如何在不使用班次的情况下找到 TMax

发布于 2024-12-03 01:21:09 字数 634 浏览 2 评论 0原文

仅使用

 ! ~ & ^ | +

如何确定 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

原文

Using ONLY

 ! ~ & ^ | +

How can I find out if a 32 bit number is TMax?

TMax is the maximum, two's complement number.

My thoughts so far have been:

int isTMax(int x)
{
  int y = 0;
  x = ~x;
  y = x + x;
  return !y;
}

That is just one of the many things I have unsuccessfully have tried but I just cant think of a property of TMax that would give me TMax back. Like adding tmax to itself would be unique compared to all the other integers.

Here is the actual problem:

/*
 * 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 is 32 bits so the max signed would probably be 0x7FFFFFFF

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

多情癖 2024-12-10 01:21:09

据我所知，如果不知道该类型的最大值并进行直接比较，就无法确定特定值是否是有符号类型的最大值。这是因为签名表达式在溢出时会遇到未定义的行为。如果你的问题有答案，那就意味着存在一个严重的未解决问题的答案，这个问题已经在 SO 上流传了一段时间：如何以编程方式确定给定签名类型的最大值。

回复收藏 0 原文

和我恋爱吧 2024-12-10 01:21:09

花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。在 c 中，所有非零的 ! 将返回 0。所以!是必须的，否则我们不能保证所有数字都得到0。

第一次天真的尝试：

因为 0b0111111...1 （又名 2147483647）是唯一应该使 isTmax 返回 1 的参数code> 和 2147483647 + 1 应该是 10000000...0（又名-2147483648)

0b011111111...1 异或 0b1000000000...0 为 0b11111111111...111。因为我们必须使用 !，所以我们希望看到的是 0（又名 0b0000000000000...0）。显然，将逻辑not（又名！）应用于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

现场演示

不错，只是< code>-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) 即可。如果 x 为 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

现场演示

完成！

Spend 3 hours on this question. I know this comes from csapp's data lab and its newest requirement is

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

So, shift operator (<</>> and 0x7FFFFFFF from the accepted answer is forbidden now)

Below is my way:

TDD-style:

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

the return should be either 0 or 1. In c, ! on all nonzero will return 0. So ! is a must, otherwise, we cannot guarantee to get 0 for all numbers.

First naive try:

because 0b0111111...1 (aka 2147483647) is the only argument that should make isTmax return 1 and 2147483647 + 1 should be 10000000...0(aka -2147483648)

0b011111111...1 xor 0b1000000000...0 is 0b11111111111...111. Because we must use !, what we hope to see is 0(aka 0b0000000000000...0). Obviously, apply logic not(aka !) to 0b1111111...1), then we will get 0b000000000000):

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

let's printf it

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

Not bad, only -1 doesn't work as we expected.

second try:

Let's compare -1 and 2147483647

11111111111111111111111111111111
01111111111111111111111111111111

We can find -1 + 1 = 0 while 2147483647 + 1 = -2147483648. Emphasize again, what we want is diff -1 and 2147483647, because both of them return 1 as above shows. Look back to the property of logic not in c: all nonzero will return 0, so !-2147483648 == 0 and !(-1 + 1) != 0. Just modify left part of x ^ (x + 1)(x) into x + !(x + 1). If x is 2147483647, x + !(x + 1) will equal to x.

Run again:

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

1

0

live demo

Done!

回复收藏 0 原文

分開簡單 2024-12-10 01:21:09

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;
}

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;
}

回复收藏 0 原文

过期以后 2024-12-10 01:21:09

无班次解决方案。意识到利用 !(0b01111 + 1 = 0b10000) = 0 和 !(0b11111 + 1 = 0b00000) = 1 的属性特别棘手。这个问题花了我很长时间。

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

int isTmax(int x) {

  int a = ~((x + 1) ^ x);
  int b = !(x + 1); 
  int c = !(a + b);

  return c;
}

No shifts solution. Realizing to take advantage of the property that !(0b01111 + 1 = 0b10000) = 0 and !(0b11111 + 1 = 0b00000) = 1 is particularly tricky. This problem took me a long time.

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

int isTmax(int x) {

  int a = ~((x + 1) ^ x);
  int b = !(x + 1); 
  int c = !(a + b);

  return c;
}

回复收藏 0 原文

以可爱出名 2024-12-10 01:21:09

也许是这样的？
0x7FFFFFFF 是最大正符号 32 位二进制补码数。

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

我不确定，您可能需要将其转换为未签名才能正常工作。

Something like this perhaps?
0x7FFFFFFF is the maximum positive signed 32 bit two's complement number.

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

I am not sure, you may need to cast it to unsigned for it to work.

回复收藏 0 原文

美男兮 2024-12-10 01:21:09

#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;
}

#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;
}

回复收藏 0 原文

小嗲 2024-12-10 01:21:09

如果是 Tmax ： 011111.....

然后我们将其与 10000 进行异或...

我们得到 11111...

然后我们 ~ 得到所有 0 = 0 , !0 我们得到 1：

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

if it is Tmax : 011111.....

then we xor it with 10000....

we get 11111....

then we ~ to get all 0s = 0 , !0 we get 1:

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

回复收藏 0 原文

错爱 2024-12-10 01:21:09

这是基于最新要求的简短答案（即，没有变化，也没有大的常数）。

x + 1 = 0x80000000;
x + (x + 1) = 0xffffffff;
!(~(x + (x + 1))) = 1;
/* Only -1 would fail so we need to explicitly exclude it.*/

最终答案。

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

Here's a shorter answer based on the newest requirements (i.e., no shifts and no big constants).

x + 1 = 0x80000000;
x + (x + 1) = 0xffffffff;
!(~(x + (x + 1))) = 1;
/* Only -1 would fail so we need to explicitly exclude it.*/

Final answer.

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

回复收藏 0 原文

~没有更多了~