C++ 如何在不使用班次的情况下找到 TMax
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7300650/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find TMax without using shifts
提问by David
Using ONLY
仅使用
! ~ & ^ | +
How can I find out if a 32 bit number is TMax?
如何确定 32 位数字是否为 TMax？
TMax is the maximum, two's complement number.
TMax 是最大值，二进制补码数。
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.
这只是我尝试过的许多失败的事情之一，但我想不出 TMax 的属性可以让我返回 TMax。与所有其他整数相比，将 tmax 添加到自身是唯一的。
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
int 是 32 位所以最大有符号可能是 0x7FFFFFFF
采纳答案by Ben Goodrich
Something like this perhaps? 0x7FFFFFFF is the maximum positive signed 32 bit two's complement number.
也许是这样的？0x7FFFFFFF 是最大的正符号 32 位二进制补码数。
int isTMax(int x){
return !(x ^ 0x7FFFFFFF);
}
I am not sure, you may need to cast it to unsigned for it to work.
我不确定，您可能需要将其转换为未签名才能工作。
回答by R.. GitHub STOP HELPING ICE
As far as I know, there is no way to determine if a particular value is the max value of a signedtype without already knowing the maximum value of that type and making a direct comparison. This is because signed expressions experience undefined behavior on overflow. If there were an answer to your question, it would imply the existence of an answer to a serious unsolved problem that's been floating around on SO for some time: how to programmatically determine the max value for a given signed type.
据我所知，如果不知道该类型的最大值并进行直接比较，就无法确定特定值是否是有符号类型的最大值。这是因为签名表达式在溢出时会遇到未定义的行为。如果您的问题有答案，则意味着存在一个严重未解决问题的答案，该问题在 SO 上已经存在了一段时间：如何以编程方式确定给定有符号类型的最大值。
回答by N.W.
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;
}
回答by u6949852
Spend 3 hours on this problem. I know this problem comes from csapp's data lab and its newest requirement is
花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
So, shift operator(<</>>and 0x7FFFFFFFfrom accepted answer is forbidden now)
所以，移位运算符（<</>>和0x7FFFFFFF来自接受的答案现在被禁止）
Below is my way:
下面是我的方法：
TDD-style:
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
the return should be either 0or 1. In, c, !+ all nonzero will return 0. So !is a must, otherwise we cannot guarantee getting 0for all numbers.
回报应该是0或1。在, c, !+ 所有非零将返回0. 所以!是必须的，否则我们不能保证获得0所有数字。
First naive try:
第一次天真尝试：
because 0b0111111...1(aka 2147483647) is the only argument which should make isTmaxreturn 1and 2147483647 + 1should be 10000000...0(aka -2147483648)
因为0b0111111...1(aka 2147483647) 是唯一应该isTmax返回的参数1并且2147483647 + 1应该是10000000...0(aka -2147483648)
0b011111111...1 xor 0b1000000000...0is 0b11111111111...111. Because we must use !, what we hope to see is 0(aka 0b0000000000000...0). Obviously, just apply logic not(aka !) to 0b1111111...1), then we will get 0b000000000000):
0b011111111...1 xor 0b1000000000...0是0b11111111111...111。因为我们必须使用!，所以我们希望看到的是0（又名0b0000000000000...0）。显然，只需将逻辑而不是（又名!）应用于0b1111111...1)，我们就会得到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
1
0
1
0
Not bad, only -1doesn't work as we expected.
不错，只是-1不像我们预期的那样工作。
second try:
第二次尝试：
Let's compare -1and 2147483647
让我们比较-1和2147483647
11111111111111111111111111111111
01111111111111111111111111111111
1111111111111111111111111111111
01111111111111111111111111111111
We can find -1 + 1 = 0while 2147483647 + 1 = -2147483648. Emphasize again, what we want is diff -1and 2147483647, because both of them return 1as above shows. Look back to the protety of logic notin c: all nonzero will return 0, so !-2147483648 == 0and !(-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.
我们可以找到-1 + 1 = 0while 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。
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
0
0
1
0
0
0
Done!
完毕！
回答by XueYu
if it is Tmax : 011111.....
如果是 Tmax : 011111 .....
then we xor it with 10000....
然后我们用 10000 异或它......
we get 11111....
我们得到 11111....
then we ~ to get all 0s = 0 , !0 we get 1:
然后我们 ~ 得到所有 0 = 0 , !0 我们得到 1:
int isTmax(int x) {
return !(~((1 << 31) ^ x ));
}
回答by DigitalRoss
#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;
}
