30

I want to implement f(int x) { return x == 0 ? 0 : 1; } in Java.

In C, I'd just "return !!x;", but ! doesn't work like that in Java. Is there some way to do it without conditionals? Without something cheesy like an unrolled version of

int ret = 0; for (int i = 0; i < 32; i++) { ret |= ((x & (1 << i)) >>> i); }

or

try { return x/x; } catch (ArithmeticException e) { return 0; }

)

EDIT:

So, I did a microbenchmark of three different solutions:

  1. my return x/x catch solution,
  2. the obvious x==0?0:1 solution, and
  3. Ed Staub's solution: (x|-x) >>> 31.

The timings for random int inputs (the whole int range) were: 

1. 0.268716 2. 0.324449 3. 0.347852

Yes, my stupid x/x solution was faster by a pretty hefty margin. Not very surprising when you consider that there are very few 0's in it, and in the vast majority of cases the fast path is taken.

The timings for the more interesting case where 50% of inputs are 0: 

1. 1.256533 2. 0.321485 3. 0.348999

The naive x==0?0:1 solution was faster by about 5% than the clever one (on my machine). I'll try to do some disassembly tomorrow to find out why.

EDIT2: Ok, so the disassembly for the conditional version is (excluding book-keeping):

testl rsi,rsi setnz rax movzbl rax,rax

The disassembly for (x|-x)>>>31 is:

movl rax,rsi negl rax orl rax,rsi sarl rax,#31

I don't think anything else needs to be said.

Improve this question
12
  • 1
    ...tricky question, but a good one... Commented Jul 8, 2011 at 18:11
  • 19
    Why do you want to avoid a simple conditional expression? Commented Jul 8, 2011 at 18:15
  • 3
    @Jim Garrison, avoiding branching could be considered to be more multi-processor/multi-gpu friendly. Who knows what kind of toaster he's going to run the code on. Commented Jul 8, 2011 at 20:20
  • 6
    @Crom, so what is the motivation for this? Commented Jul 8, 2011 at 21:01
  • 1
    @Dilum Ranatunga, @Alexander, @Jim Garrison: no toaster :) - it's just for fun. Commented Jul 9, 2011 at 1:42

8 Answers 8

Reset to default
41

Ok, shortest solution without conditional is probably:

return (i|-i) >>> 31;
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

@Orion how about return (i|-i) >>> java.math.BigInteger.valueOf(Integer.MAX_VALUE).bitLength();
@eng.Fouad, talk about taking a quick solution and trashing it with no fewer than 2 function calls.
If you really want to get rid of the majick 31, the right way is return (i|-i) >>> (Integer.SIZE-1);. I certainly wouldn't do it out of forward-compatibility concerns, though - only to make it clear where the 31 came from. There is far, far too much code that would break for them to ever change the size of an int.
@Eng.Fouad - Who would have thought a dozen characters would be worth 300+ rep?
@Ed Staub: It's not the dozen characters. It's knowing what to do with them.
|
11

Here is a solution:

public static int compute(int i) { return ((i | (~i + 1)) >> 31) & 1; // return ((i | -i) >> 31) & 1 }

EDIT:

or you can make it more simple:

public static int compute(int i) { return -(-i >> 31); // return -i >>> 31 }

EDIT2:

last solution fails with negative numbers. Take a look at @Ed Staub's solution.

EDIT3:

@Orion Adrian OK, here is a general solution:

public static int compute(int i) { return (i|-i) >>> java.math.BigInteger.valueOf(Integer.MAX_VALUE).bitLength(); }
Improve this answer

7 Comments

@Eng.Fouad: Nice! I could feel this would be done with | and ~, but I couldn't quite think of it myself. Although, if you replace (~i + 1) with -i, it would be a bit better.
@Eng.Fouad: Your revised version doesn't work. compute(1) would return -1, for example. The best answer is probably (1|-1)>>>31, pointed out by Ed.
@CromTheDestroyer compute(1) would return 1 and you're right .. @Ed Staub's solution is much better
See, i knew there was something you could involving bits!
@Orion Adrian: When would that happen? With Java's backwards compatibility, I doubt they'd change the bit length of an int. They'd probably just add a new type superlong for 128 bit numbers.
|
8 
int f(int x) { return Math.abs(Integer.signum(x)); }

The signum() function returns the sign of the number as -1, 0 or 1. So all what's left is to turn -1 into 1, which is what abs does.

Improve this answer

6 Comments

If the objection to a conditional was based on performance concerns, surely this cure is worse than the disease.
@Ed, I for one did not see any mention of performance in the original question. Indeed, the divide and catch example gave me the impression of some entirely different motivation.
This is kinda cheating since Math.abs has a conditional internally : p
int f(int x) {Integer.signum(x) & 1;} would be a little bit-twiddlier.
I wonder why people upvote this.... Math.abs(i) does return (a < 0) ? -a : a; internally... isn't that what the question is trying to avoid?
|
7

The signum function implements it this way

return (i >> 31) | (-i >>> 31);

so, just add another bitwise operation to return 0 or 1

return ((i >> 31) | (-i >>> 31)) & 1;
Improve this answer

Comments

7

All of these solutions seem to suffer from the vice of taking varying degrees of effort to understand. That means the programmer who must later read and maintain this code will have to expend unnecessary effort. That costs money.

The expression

(x == 0)? 0:1

is straightforward and simple to understand. It's really the right way to do this. The use of an exception in the ordinary run of code is downright ghastly. Exceptions are for handling circumstances beyond programmer control, not for ordinary routine operations.

Improve this answer

7 Comments

Totally correct, except where very extreme performance requirements pertain, as in image processing. In that case, using the solution I suggested in a "final" method should eliminate any branching that might cause a pipeline stall. But I think this was meant mostly as a puzzle.
@Ed, on the right hardware with the right hotspot, the conditional can evaluate faster than the two operation bit math. Also, on hardware that does pay for the conditional, the ? 0 : 1 expression is a relatively easy expression to optimize at the compiler/hotspot level, right?
@Dilum, of course there's theoretically hardware where your mileage may differ. And if hotspot recognized the entire expression, it might JIT-compile it down to a single instruction on some theoretical machine that had such an instruction. But on most machines, the expression (i|-i) >>> 31 should JIT-compile it down, with no optimization at all, down to 3 instructions (negate, or, shift), with no memory accesses beyond the initial load and final store, with no branches, on nearly all machines. That's pretty hard to beat. cont...
The best I'd expect with branching, on most machines, would be 4 - negate, or, branch-if-0 (with potential stall), and load. Add another fraction if the compiler isn't willing to use two return statements.
@ncmathsadist: Eh - does no one read tags? I clearly marked this "code-kata" just to avoid this sort of answer. @Ed Staub is right - it's just a puzzle. Also, why are you mentioning my implementation with the exception? I clearly stated that was an example of what I didn't want.
|
1

I wonder what the compiler would turn this into...

class kata { public static int f(int x){ return -(Boolean.valueOf(x==0).compareTo(true)); } public static void main(String[] args) { System.out.println(f(0)); System.out.println(f(5)); System.out.println(f(-1)); } }

http://ideone.com/ssAVo

Improve this answer

Comments

0

This question reduces down to: "Is there a way to map boolean true,false to int 1,0 respectively without writing the conditional."

In Java, there is no standardized treatment of true as 1. The closest is use of -1. So as @Ed says, the ternary operator is as succinct as you get.

Improve this answer

2 Comments

He was asking for fast, not succint.
If you read my question, you'll see I wasn't asking for fast, nor succinct. I was just asking for a bit-twiddly way of eliminating the conditional, since I find this sort of thing fun.
0

If you wanted a boolean, i think:

return x == x >>> 1

Would do it, because the only number whose set bits don't move when shifted is one with no set bits.

Under the hood, the bytecode actually uses 1 and 0 for true and false, but i don't know of any way to turn a Java language boolean value into its corresponding int value without some sort of conditional.

Improve this answer

4 Comments

If he wanted a boolean, he could have written return x == 0.
Yeah. I had some sort of idea bouncing around in my head about bit patterns, but by the time it came out it was nonsense. I'm going to leave this answer undeleted in case anyone needs a laugh.
@Rotsor: No, because that's a logical shift right, not an arithmetic shift right. It works. It's pointless, but it works.
Ah, sorry, I thought it was a circular shift right (ROR). I'm deleting my comment.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.