Using bitwise operators and I suppose addition and subtraction, how can I check if a signed integer is positive (specifically, not negative and not zero)? I'm sure the answer to this is very simple, but it's just not coming to me.
This fails for zero, which is neither positive nor negative.
caf
2010-09-16 22:57:55
But if the most significant bit is 0 and all the other bits are zero, it returns 'positive' but zero is supposed to be excluded.
Jonathan Leffler
2010-09-16 22:58:35
You are right, though he could check for someInt == 0;
Alex
2010-09-16 23:05:33
+1
A:
Consider how the signedness is represented. Often it's done with two's-complement or with a simple sign bit - I think both of these could be checked with a simple logical and.
crazyscot
2010-09-16 22:52:43
A:
Check that is not 0 and the most significant bit is 0, something like:
int positive(int x) {
return x && (x & 0x80000000);
}
Ssancho
2010-09-16 22:55:03
Ssancho
2010-09-17 17:19:18
+3
A:
If you can't use the obvious comparison operators, then you have to work harder:
int i = anyValue;
if (i && !(i & (1U << (sizeof(int) * CHAR_BIT - 1))))
/* I'm almost positive it is positive */
The first term checks that the value is not zero; the second checks that the value does not have the leading bit set. That should work for 2's-complement, 1's-complement or sign-magnitude integers.
Jonathan Leffler
2010-09-16 22:56:29
Unfortunately, it has undefined behaviour ;) - 2 raised to the power of `(sizeof(int) * CHAR_BIT - 1)` is certainly not representable in `int`.
caf
2010-09-16 23:05:37
@caf: that can be addressed by converting the 1 that is shifted to `unsigned int` with a U suffix...which means that `i` will be converted to `unsigned int` too. Bit-shifting should normally be done on unsigned quantities anyway.
Jonathan Leffler
2010-09-16 23:58:16
Yep, that fixes the UB - now you just have to worry about the (even more theoretical!) case where `int` and `unsigned int` have the same number of value bits...
caf
2010-09-17 00:13:28
@R: It does, unfortunately - in 6.2.6.2: "if there areM value bits in the signed type and N in the unsigned type, then M <= N" - implying that you could have (for example) `int` with range -131072 to 131071 and `unsigned int` with range 0 to 131071.
caf
2010-09-17 00:29:49
@caf: did you mean 'where `int` and `unsigned int` have _different_ numbers of bits'? I don't think that's a problem because I think the standard requires them to have the same number of bits.
Jonathan Leffler
2010-09-17 00:35:37
@Jonathan: No, the problem is when they have an equal number of *value* bits (typically, the unsigned type has one more value bit than the corresponding signed type). When this is the case, your shift of `1U` may end up with 0 as the result; and also the "usual arithmetic conversion" of `i` to `unsigned` will map negative and positive values onto the same range of values in the `unsigned` type.
caf
2010-09-17 00:59:52
Generally a shift with a calculation using `sizeof` will not always work since the width of a type and its size are not forcebly related in that way. There may be padding bits. I think an expression like `(((unsigned)-1u)/2u)+1u)` would be more portable. Though this also supposes that `signed` and `unsigned` have the same width.
Jens Gustedt
2010-09-17 06:38:21
+4
A:
If you really want an "is strictly positive" predicate for int n without using conditionals (assuming 2's complement):
-nwill have the sign (top) bit set ifnwas strictly positive, and clear in all other cases exceptn == INT_MIN;~nwill have the sign bit set ifnwas strictly positive, or 0, and clear in all other cases includingn == INT_MIN;- ...so
-n & ~nwill have the sign bit set if n was strictly positive, and clear in all other cases.
Apply an unsigned shift to turn this into a 0 / 1 answer:
int strictly_positive = (unsigned)(-n & ~n) >> ((sizeof(int) * CHAR_BIT) - 1);
EDIT: as caf points out in the comments, -n causes an overflow when n == INT_MIN (still assuming 2's complement). The C standard allows the program to fail in this case (for example, you can enable traps for signed overflow using GCC with the-ftrapv option). Casting n to unsigned fixes the problem (unsigned arithmetic does not cause overflows). So an improvement would be:
unsigned u = (unsigned)n;
int strictly_positive = (-u & ~u) >> ((sizeof(int) * CHAR_BIT) - 1);
Matthew Slattery
2010-09-16 23:16:46
Strictly, that only works on 2's complement arithmetic (which are, I grant you, the practically significant systems). With a negative zero (1's complement or sign-magnitude), your assertions are not valid.
Jonathan Leffler
2010-09-17 00:04:19
@Jonathan: if you cast to `unsigned` before applying the `~` operator, then it works for all systems.
R..
2010-09-17 00:22:15
Now it just has the problem in the (admittedly, very theoretical) "`int` has as many value bits as `unsigned int`" case ;)
caf
2010-09-17 01:43:22
@caf: And the problem that `sizeof` is not the right thing to compute the width of a type... there may be padding bits. See my comment to Jonathan's answer.
Jens Gustedt
2010-09-17 07:29:50