Which one-bit integer has more significant bit?

Question

I have two unequal integers which contain only one nonzero bit. How to test which integer has a more significant bit?

Example:

test(0b1000_0000, 0b0100_0000); // Should return true
test(0b0010_0000_0000, 0b0100_0000_0000); // Should return false

What is the most efficient implementation of test?

@rkosegi Integers are signed in Java. This will not work for negative integers. — ZhekaKozlov, Jan 29 '17 at 05:54

Stephen C · Answer 1 · 2017-01-29T06:00:41.770

4

Hint: The "clean" way to do it is to use either Integer.compareUnsigned or Integer.numberOfLeadingZeros.

(Caveat: the "unsigned" methods are only available in Java 8 and later ...)

What is the most efficient implementation of test?

The answer to the efficiency part of your question will be platform specific. If you really care, benchmark the various alternatives that people provide.

edited Jan 29 '17 at 06:00

answered Jan 29 '17 at 05:55

Stephen C

698,415
94
811
1,216

It's actually hard to benchmark this because any reasonable implementation is fast enough that it gets lost in the overhead. – D M Jan 29 '17 at 06:38
1

You can solve this using an appropriately designed benchmark implemented using a good microbenchmark framework – Stephen C Jan 29 '17 at 06:56
Hint: do the operation a large number of times, measure total time then divide by number of repetitions. (Or don't and compare the aggregate times ...) Anyhow, 1) it is not that hard, 2) there are frameforks, and 3) if the OP cares about this kind of thing, then he *should learn* to do this kind of benchmarking. – Stephen C Jan 29 '17 at 07:09
yeah, I did the operation a billion times to make it actually take three seconds, but I suspect lots of that is just memory access and loop overhead. And the order I do my tests in still has an effect even after I "warm up" by calling each method a hundred million times first. – D M Jan 29 '17 at 07:17
@DM - If I were you ... I would use a reputable Java benchmarking framework. See the last rule of benchmarking - http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java. The fact that the order of the tests matters means you are doing something wrong. – Stephen C Jan 29 '17 at 13:11

score 0 · Accepted Answer · answered Jan 29 '17 at 05:52

0

I think this is the most efficient implementation. And this works for negative integers too:

static boolean test(int int1, int int2) {
    return ((int2 - 1) & int1) == 0;
}

answered Jan 29 '17 at 05:52

ZhekaKozlov

36,558
20
126
155

1

What is this witchcraft – shmosel Jan 29 '17 at 06:00
1

Subtracting one from a number that has only one set bit turns off the set bit, but turns on all the following bits, as in 10000 → 1111. Anding that with the other number that also has only one set bit will be nonzero only if the set bit was one of the following bits of the original number. – Chai T. Rex Jan 29 '17 at 07:20

Which one-bit integer has more significant bit?

2 Answers2