sign function in C using bit operators only

Question

I'm trying to implement a sign function using only bitwise operators. I know that if I just want to extract the sign bit of a signed integer, I can do: (x >> 31) & 1.

Also, I understand that conditionals can be written as boolean expressions:

if(x) a=y else a=z which is equivalent to a = x ? y:z can be rewritten as:

a=( (x<<31) << 31 ) & y + ( !x << 31) >> 31) & z, assuming x=1 or 0.

This problem gets a little tricky though because I have 3 conditional scenarios:
return 1 if positive, 0 if zero, and -1 if negative.

I was thinking that in order to do this properly, I need to use ! operator and the fact that !0x<nonzero #>=0, !0x0=1, !0x1=0.

So I came up with something like this, which is incorrect:

/*                                                                              
 * sign - return 1 if positive, 0 if zero, and -1 if negative                   
 *  Examples: sign(130) = 1                                                     
 *            sign(-23) = -1                                                    
 *  Legal ops: ! ~ & ^ | + << >>                                                                          
 */
int sign(int x) {
    return (x>>31) & -1 ) + ( !( !x >> 31 ) & 1;
}

I think I have all the pieces but just not quite sure how to put them all together. Any help is appreciated.

Thank you.

Why not just write the obvious code and let the compiler optimizer do the hard work for you? — Greg Hewgill, Jul 20 '14 at 23:25
Using the compiler to get an answer to a homework problem is not necessarily wrong. :) — Greg Hewgill, Jul 20 '14 at 23:27
That's a rather daft thing to try. (x > 0 ? 1 : x < 0 ? -1 : 0) is a perfectly fine, portable and readable solution. Anything more complicated is nonsense. — gnasher729, Jul 20 '14 at 23:27
So what? This is a programming site, not a site for masochists. — gnasher729, Jul 20 '14 at 23:29
Do you know bit twiddles? https://graphics.stanford.edu/~seander/bithacks.html. My comment is just a contribution, not an answer. — JayInNyc, Jul 20 '14 at 23:38
OP: Using (x >> 31) & 1 to extract the sign bit is, depending on the C implementation and the number of value bits in an int, either implementation defined, or undefined behaviour, or wrong. — gnasher729, Jul 20 '14 at 23:39
Any of these clever "bit hacks", especially those involving shifting to the right, are just waiting to be invalidated by an aggressive compiler optimizer. *Write the obvious code.* — Greg Hewgill, Jul 20 '14 at 23:41

score 12 · Accepted Answer · answered Jul 20 '14 at 23:31

12

The bit hacks page suggests this expression:

sign = (v != 0) | (v >> 31);

It can be rewritten without != like this:

sign = (!!v) | (v >> 31);

(demo on ideone).

I prefer this expression that does not use bit manipulation, though (from the same page).

sign = (v > 0) - (v < 0);

answered Jul 20 '14 at 23:31

Sergey Kalinichenko

714,442
84
1,110
1,523

This returns 1 if v == 0. – McLovin Jul 20 '14 at 23:37
3

The first two are badly non-portable, the last one is perfectly fine and correct. With the additional benefit that it works for all real types, including signed, unsigned, all sizes, and floating point. – gnasher729 Jul 20 '14 at 23:43
@gnasher729 The first two can be made less non-portable with the expression from the linked page (i.e. `sizeof(int)*BITS_PER_BYTE-1`, where `BITS_PER_BYTE` defines the number of bits in a byte on a target computer). I do love the last one the most, that's why I mentioned it, even though I think it's against OP's rules. – Sergey Kalinichenko Jul 20 '14 at 23:45
`BITS_PER_BYTE`? Why not the standard `CHAR_BIT`? – Deduplicator Jul 20 '14 at 23:47
@Deduplicator Because `BITS_PER_BYTE` is self-explanatory, while `CHAR_BITS` [requires a lookup](http://stackoverflow.com/q/3200954/335858). – Sergey Kalinichenko Jul 20 '14 at 23:49
Thank you @dasblinkenlight . The second equation is what I was looking for. Is there a way to systematically come up with these solutions? It's so convoluted to me. – user1527227 Jul 21 '14 at 00:24
1

`v >> 31` causes implementation-defined behaviour – M.M Jul 21 '14 at 00:27
@user1527227 Unfortunately, bit twiddling is more an art than a science. My strategy has been to bookmark the link from the first paragraph of the answer, and refer to it for all my bit manipulation needs. – Sergey Kalinichenko Jul 21 '14 at 00:29
@user1527227 It is convoluted, your question is "How do I do this simple task in a convoluted manner" – M.M Jul 21 '14 at 00:30
@dasblinkenlight fair enough. Thank you. Just thought I'd try ;). – user1527227 Jul 21 '14 at 00:31

JohnB · Answer 2 · 2014-07-21T00:22:01.687

This one also works if the right shift is a binary one, rather than an arithmetic one:

unsigned int x;
static_assert (sizeof(x) == 4);

(~ (!!x)) + 1 + ( ( (x+0x7FFFFFFF) & 0x80000000 )  >> 30 )

or

(~ (!!x)) + 1 + ( ( !!( (x+0x7FFFFFFF) & 0x80000000 ) ) << 1 )

Explanation:

(~ (!!x)) + 1 gives you 0 for x==0 and -1 otherwise.

( ( (x+0x7FFFFFFF) & 0x80000000 ) >> 30 ) gives you 2 for x>0 and 0 otherwise.

sign function in C using bit operators only

2 Answers2

Linked

Related