Create a function which returns 1 if x < 0, returns 0 otherwise using only bitwise operations

Question

This is the code i've been able to come up:

isNegative(int a)
    int result;
    result = (a >> 31);
    result = result & 1;

This works fine for all cases except for, 0x80000000. Please help as to how I can fix this code to be correct for all cases.

`0x80000000` is negative (for a 32-bit int), and your function does return 1 for it. What is the problem? — Nelfeal, Oct 02 '22 at 13:00
https://stackoverflow.com/questions/11438794/is-the-size-of-c-int-2-bytes-or-4-bytes probably shouldn't assume a 32 bit `int`, though that might be accurate on some systems — erik258, Oct 02 '22 at 13:01
Actually, since right-shifting a negative integer is implementation defined, maybe there is your problem. — Nelfeal, Oct 02 '22 at 13:01
Does this answer your question? [Checking whether a number is positive or negative using bitwise operators](https://stackoverflow.com/questions/3779202/checking-whether-a-number-is-positive-or-negative-using-bitwise-operators) — Paul Hankin, Oct 02 '22 at 13:30

chqrlie · Answer 1 · 2022-10-02T13:09:21.407

The code posted has implementation behavior: Right shifting a signed negative value is specified as implementation-defined by the C Standard:

6.5.7 Bitwise shift operators

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Conversely, conversion from signed int to unsigned is fully defined and right shifting the unsigned value will work as expected.

Note that if the width of the unsigned type is exactly 32 bits, masking the result of the right shift is not required. Regarding the behavior on INT_MIN: if signed integers are represented using two's complement, converting INT_MIN to unsigned produces 0x80000000, which gives 1 when shifted right by 31 bits, as expected since INT_MIN is negative.

Here is a modified version:

#include <stdint.h>

// assuming 32-bit ints
int isNegative(int32_t a) {
    uint32_t result = a;
    return result >> 31;
}

Would this work in 32-bit excess-2^31 representation? Not that I know any such implementation. — Nelfeal, Oct 02 '22 at 13:17
@Nelfeal: excess notations are not standard representations for signed integers in the C Standard. As a matter of fact, the upcoming C23 Standard will only support 2's complement representations, with or without padding bits. Note also that the most significant bit in excess notations is the complement of the sign bit: `0` for negative, `1` for positive. — chqrlie, Oct 02 '22 at 13:23

Nelfeal · Answer 2 · 2022-10-02T13:29:03.963

1

Here is an implementation that doesn't rely on implementation defined right-shifting and doesn't assume the size of an int (but assumes two's complement representation):

#include <limits.h>

int isNegative(int a) {
    return !!(a & INT_MIN);
}

edited Oct 02 '22 at 13:29

answered Oct 02 '22 at 13:08

Nelfeal

12,593
1
20
39

Interesting alternative, but does not work for non 2's complement representations – chqrlie Oct 02 '22 at 13:11
@chqrlie Pretty sure it also works in sign-magnitude and 1's complement if you consider `-0 < +0`. I suppose you could add a `&& a != -0` (or `&& a != 0`? I don't know how these representations would work with the `-0`). – Nelfeal Oct 02 '22 at 13:15
1

I'm afraid you miss somthing: `INT_MIN` has all bits set on both of these representations, so `!!(a & INT_MIN);` evaluates to `0` only for `+0` and `-0`. – chqrlie Oct 02 '22 at 13:20
@chqrlie Good point, though I think this only applies to sign-magnitude. `INT_MIN` in 1's complement should be 127 and represented as `10000000`. – Nelfeal Oct 02 '22 at 13:23
You are correct, `INT_MIN` has the same representation in ones' complement and two's complement representations, but your expression will also evaluate to `1` for `-0` which may or may not be expected. – chqrlie Oct 02 '22 at 13:27
Note however that `!` is not considered a *bitwise operation*. You could also write `return (a & INT_MIN) / INT_MIN;` but `/` is not a *bitwise operation* either. – chqrlie Oct 02 '22 at 13:31
@chqrlie True, but technically, neither is a cast to an unsigned type. The question is not well formulated in my opinion (as are many of these "only bitwise operations" questions). – Nelfeal Oct 02 '22 at 13:46
Note that there is no cast in my code, just an implicit conversion... and I agree with your assessment :) – chqrlie Oct 02 '22 at 13:59

Create a function which returns 1 if x < 0, returns 0 otherwise using only bitwise operations

2 Answers2