# How to find TMax without using shifts

1

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

c++
c
binary
logic
bit-manipulation

4

As far as I know, there is no way to determine if a particular value is the max value of a signed type 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.

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

Spend 3 hours on this problem. I know this problem 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 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, `!` + all nonzero will return `0`. So `!` is a must, otherwise we cannot guarantee getting `0` for all numbers.

### First naive try:

because `0b0111111...1`(aka `2147483647`) is the only argument which 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, just 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 protety 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

0

0

`live demo`

Done!

0

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
``````#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)) ? "" : " not");
return 0;
}
``````
0

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

User contributions licensed under CC BY-SA 3.0