Fight the Powah



  • At the end of a source file full of complicated math methods:

    private Boolean isPowerOfTwo(Integer value) {
        if (value == 1) {
            return true;
        } else if (value == 0 || value % 2 != 0) {
            return false;
        }
        return isPowerOfTwo(value/2);
    }

    It got replaced with a bitwise one-liner.



  • How do you represent that in one line?  I can't think of any way to calculate that in one line unless you've got an intrinsic that resolves to the BSF assembly instruction...



  • (value >> 1) << 1 == value

    ?

    Bah, no ... that's just divisible by two ... much like

    value & 0x01 == 0

     



  • Like this?

    [code]for (;; value = value>>1) { if (value < 2) return value; }[/code]



  • I would like to point out that the original WTF code is 20,000 times more readable than both one-liner alternatives posted so far.



  • return (value & 0x01);



  • @Melnorme said:

    Like this?

    <font face="Lucida Console" size="2">for (;;x = x>>1) { if (x<2) return x; }</font>

    That doesn't work, 1010 will return true. If it's a power of 2 then there will be only one 1 in the binary representation of the argument.

    @blakeyrat said:

    I would like to point out that the original WTF code is 20,000 times more readable than both one-liner alternatives posted so far.

    How about:

    private Boolean isPowerOfTwo(Integer value) {
    //one-liner
    }


  •  return (value&(value-1))==0; I think



  • @Melnorme said:

    Like this?

    <font face="Lucida Console" size="2">for (;; value = value>>1) { if (value < 2) return value; }</font>

     

    First, stuffing a loop into one line is cheating. And second, I don't see how that will actually calculate whether or not something is a power of 2.

    Now, if you have a BSF (assembly instruction that returns the number of the least significant bit that's set to 1) intrinsic, it's trivial:

    return value == 1 << BSF(value);

    But I'm not aware of any language that has that...



  • My version:

    return value == 1 || value == 2 || value == 4 || value == 8 || value == 16 || value == 32 || value == 64 || value == 128 || value == 256 || value == 512 || value == 1024 || value == 2048 || /* snip */ || value == 2147483648;


  • Oops. Right you are.



  • @dtfinch said:

     return (value&(value-1))==0; I think

    close

    return (value > 0) && (value & (value - 1) == 0)



  • @Kaosadvokit said:

    return (value > 0) && (value & (value - 1) == 0)

    Yeah, that's the one.



  • Geek pr0n, gotta love it.


  • Discourse touched me in a no-no place

    @Mason Wheeler said:

    How do you represent that in one line?
    http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2



  • @Kaosadvokit said:

    return (value > 0) && (value & (value - 1) == 0)
    Close.  Problem is "==" has higher precedence than "&" so what you are really doing there is:

    return (value > 0) && (value & ((value - 1) == 0))

    When what you want is:

    return (value > 0) && ((value & (value - 1)) == 0)

     



  • return (n > 0 && (n & (n - 1)) == 0);

    works too.

    Oh, and I changed the method signature. Pretty silly for it to be taking an Integer instead of int; correct me if I'm wrong, but isn't autoboxing done at runtime, not compile-time?



  • @C-Octothorpe said:

    Geek pr0n, gotta love it.

    Hells yeah, I especially love the deleted scene where..


    Oh, you were talking about the goddamn bit-twiddling.



  • @Mr. DOS said:

    Pretty silly for it to be taking an Integer instead of int; correct me if I'm wrong, but isn't autoboxing done at runtime, not compile-time?

    Pointless micro-optimization makes baby Jesus cry.


  • ♿ (Parody)

    @morbiuswilters said:

    @Mr. DOS said:
    Pretty silly for it to be taking an Integer instead of int; correct me if I'm wrong, but isn't autoboxing done at runtime, not compile-time?

    Pointless micro-optimization makes baby Jesus cry.

    How does he feel about NullPointerExceptions?



  • @morbiuswilters said:

    @Mr. DOS said:
    Pretty silly for it to be taking an Integer instead of int; correct me if I'm wrong, but isn't autoboxing done at runtime, not compile-time?
    Pointless micro-optimization makes baby Jesus cry.



    TRWTF are the users on the DailyWTF!


  • @Mr. DOS said:

    @Kaosadvokit said:

    return (value > 0) && (value & (value - 1) == 0)

    Yeah, that's the one.

     

     

    And, of corse, for negatives:

     

     

    if(value < 0)

       value = value + 1

     return (value & (value - 1) == 0)

     

    But now it is not one line anymore. But the original code was both more readable (not that important for a function that short) and able to deal with negative numbers, so the one-liner is wrong.



  • @Mcoder said:

    and able to deal with negative numbers

    ...praytell, by what magic have you found a negative number to be a power of 2?



  • @boomzilla said:

    @morbiuswilters said:
    @Mr. DOS said:
    Pretty silly for it to be taking an Integer instead of int; correct me if I'm wrong, but isn't autoboxing done at runtime, not compile-time?

    Pointless micro-optimization makes baby Jesus cry.

    How does he feel about NullPointerExceptions?

    Better than SharpRomanPointerExceptions.


    As for the code: NPEs can happen either way. If the signature requires an int and a null Integer is passed, the NPE is thrown at the point at invocation. If the signature requires an Integer and a null Integer is passed, it would blow up at the first use of the Integer. (Unless you wanted to implement some kind of type coercion which returns false for a null Integer. Then you would not have an NPE.)



  • @Mr. DOS said:

    @Mcoder said:

    and able to deal with negative numbers

    ...praytell, by what magic have you found a negative number to be a power of 2?

     

    It is probably considered heretic in your religion/culture, but there are whispers of numbers unimaginably imaginary...

    Then again, that would make the perfect power of two test:

    <code>

    private Boolean isPowerOfTwo(Integer value) {
    return value != 0;
    }

    </code>


  • ♿ (Parody)

    @Mcoder said:

    And, of corse, for negatives:

    So, can you please cite a negative number and its logarithm, base 2? I am eager to learn this new mathematics. Do you also have anything on division by zero?


  • BINNED

    @this_code_sucks said:

    TRWTF are the users on the DailyWTF!
    Yes, and coming to that conclusion is a rite of passage for new DailyWTF users. Congratulations on reaching an important milestone.


  • ♿ (Parody)

    @morbiuswilters said:

    As for the code: NPEs can happen either way. If the signature requires an int and a null Integer is passed, the NPE is thrown at the point at invocation. If the signature requires an Integer and a null Integer is passed, it would blow up at the first use of the Integer. (Unless you wanted to implement some kind of type coercion which returns false for a null Integer. Then you would not have an NPE.)

    So, is the bug with isPowerOfTwo or the calling code? If they just use an int, it would be obvious. In reality, these guys are probably using Integers everywhere. A math library is the sort of place where crazy micro-optimizations are most likely to make sense, given the way these things tend to be used (YMMV, of course). And anyone using a recursive function and division operations like this probably has bigger optimization issues (although probably the compiler is smart enough to turn that into a bitwise operation).

    But returning false seems like the correct thing to do from the name of the function.

    I wonder what the JIT compiler would do if you added a null check at the beginning of the function. Would it be smart enough, on recursive calls, to jump past that?



  • @boomzilla said:

    So, can you please cite a negative number and its logarithm, base 2?

    Negative negative two and one, respectively. I'll take my Fields medal now. Although, I'd prefer a check made out to "cash"-- Oh, you don't do that? Any idea what the pawn value of one of these babies is? I ask because I have this friend.. who also has a Fields medal..

    @boomzilla said:

    Do you also have anything on division by zero?

    I have some very intriguing comics I drew about division by Zorro, if you find that useful.


    He divides them with his penis. They're pornographic comics.



  • @dtfinch said:

     return (value&(value-1))==0; I think

     

     

    Thanks, dtfinch, you have it right. The other attempts? Kind of... bizzare. At least the original code worked! NONE of the suggestions before yours did. In Scheme

            (define (is-power-of-2 x) (= 0 (bitwise-and x (- x 1)))

    (is-power-of-2 0) -> #t, 0, 1, 2 are powers of 2, 3 is not, 4 is, 5, 6, 7 are not, 8 is -- feel free to fill in the test cases

    (is-power-of-2 6) -> #f

    (is-power-of-2 8) -> #t

     Note that this formulation works the same as the original.

     

    Why it works:

     A power of two represented in binary is 1 0*, that is, a single 1 followed by zero or more 0s.

    Subtracting one from this number results in 0 1*, where the pattern 1* is a number of 1s that is the same as the number of zeros in the original number (0*).

     "And"ing these gives 0 iff the original number followed the first pattern -- because a non power-of-2 number would have had at least a one bit somewhere else. This would have "stopped" the subtraction carry too early. For example, consider the 3 bit numbers (100 through 111):

    x=100 x-1=011, & -> 0

    x=110, x-1=101, & -> 100

    x=101, x-1=100, & -> 100

    x=111, x-1=110, & -> 110

     Notice the only subtraction that carries from the highest bit is the power of 2, because that one is the only one that will propagate the carry that far.

     Mind you, the original formulation was clear, and would execute in a time proportional to the number of bits in the argument. It also only used integer operations (which may be important if bitwise wasn't implemented for the particular integer implementation). It isn't bad, and I would have profiled before replacing it. The replacement ((n) & (n - 1)) == 0 requires a LOT more documentation (like this entire post).

     

     


  • ♿ (Parody)

    @lurch said:

    (is-power-of-2 0) -> #t, 0, 1, 2 are powers of 2, 3 is not, 4 is, 5, 6, 7 are not, 8 is -- feel free to fill in the test cases

    So, which power of 2 is 0?



  • @Mcoder said:

    @Mr. DOS said:

    @Kaosadvokit said:

    return (value > 0) && (value & (value - 1) == 0)

    Yeah, that's the one.

     

     

    And, of corse, for negatives:

     

     

    if(value < 0)

       value = value + 1

     return (value & (value - 1) == 0)

     

    But now it is not one line anymore. But the original code was both more readable (not that important for a function that short) and able to deal with negative numbers, so the one-liner is wrong.

     

     

    The original code simply returns FALSE for any negative number. The proof is:

     Any negative number divided by 2 gives a negative number, EXCEPT for -1/2 which gives 0.

    This means that the first clause (value == 1) will NEVER be taken.

    The only exit possible is the second clause, which will return FALSE.

    The solution will continue to divide by 2, until value is -1 in the negative case, so the routine will exit (but always with FALSE in the negative case).

    QED.

     

    So, the one liner does have the same behaviour. For any negative number (n & (n - 1)) cannot return zero. Sinply because there is at least one additional "sign" bit to the left of the significant bits. When "and"ed, this will result in at least one bit set in the result, which is, by definition, not zero.

     In fact, there is only ONE negative Integer in 2's complement that will result in zero after the anding - the most negative integer. Consider two bit integers: 00 01 10 11, (0, 1, -2, -1 as 2's complement). 10 - 01 = 01, interpreted as -2 - 1 -> 1, which is, of course, mathematically wrong), and 10 & 01 = 0, declaring the most negative integer to be a power of two.

     

     



  • @boomzilla said:

    @lurch said:
    (is-power-of-2 0) -> #t, 0, 1, 2 are powers of 2, 3 is not, 4 is, 5, 6, 7 are not, 8 is -- feel free to fill in the test cases

    So, which power of 2 is 0?


    -Infinity, of course...

    I particularly liked the way that "0 is a power of 2" appeared in the same post as "A power of two represented in binary is 1 0*, that is, a single 1 followed by zero or more 0s." It's news to me that the binary representation of 0 has a 1 in it somewhere; I obviously haven't been looking hard enough.



  •  boomzilla

     

    Yeah, you are right -- sorry, didn't "review" it before submit.

    So, the working definition would be

    (x != 0)? (x & (x - 1)) == 0 : false

     'K?

     



  • @boomzilla said:

    So, is the bug with isPowerOfTwo or the calling code? If they just use an int, it would be obvious.

    Fair enough. I think TRWTF is that Java doesn't have the concept of a not-null Object. Every time I am writing a null check at the top of a method I'm thinking to myself "Why the fuck do I have to do this? Why is the language not handling this shit for me?" Really, I think the not-null type should be the default and nullable types should be the exception.

    @boomzilla said:

    In reality, these guys are probably using Integers everywhere. A math library is the sort of place where crazy micro-optimizations are most likely to make sense, given the way these things tend to be used (YMMV, of course).

    I'm not even convinced it is more efficient. Maybe if everything they pass in is an int. (Side note: I'm more concerned about the return type of Boolean which should be bool. Now calling code has to check for nulls.)

    @boomzilla said:

    And anyone using a recursive function and division operations like this probably has bigger optimization issues (although probably the compiler is smart enough to turn that into a bitwise operation).

    I'm really not up to the state-of-the-art javac optimizations, but it seems a pretty big stretch to me for a compiler to convert recursive division into a single bitwise operation.

    @boomzilla said:

    But returning false seems like the correct thing to do from the name of the function.

    I usually don't assume things like that in Java. I'd tend to assume that if this function was passed a null that that was a mistake and an error should be thrown.

    @boomzilla said:

    I wonder what the JIT compiler would do if you added a null check at the beginning of the function. Would it be smart enough, on recursive calls, to jump past that?

    That's more believable.



  • Didn't you just say that it also gets INT_MIN wrong? Just go with (x > 0) && ((x & (x-1)) == 0), like others posted much earlier in the thread anyway.

    Or don't try to do it in a bit-twiddling one-liner which is easy to get subtly wrong. That's an option too.



  • I am disappointed that no-one has solved this using regular expressions.


  • ♿ (Parody)

    @morbiuswilters said:

    @boomzilla said:
    And anyone using a recursive function and division operations like this probably has bigger optimization issues (although probably the compiler is smart enough to turn that into a bitwise operation).

    I'm really not up to the state-of-the-art javac optimizations, but it seems a pretty big stretch to me for a compiler to convert recursive division into a single bitwise operation.

    I should have been more clear. I was talking about the modulo 2 operation. In fact, that might even be done at the byte code level. It's not explicitly division, but there's division involved (though maybe some low level optimizations turn it into bit twiddling, or subtraction or something). Although, the division by two at the end could be turned into a bit shift, too. I wasn't thinking that it would reduce the entire function to a bitwise operator.

    @morbiuswilters said:

    @boomzilla said:
    But returning false seems like the correct thing to do from the name of the function.

    I usually don't assume things like that in Java. I'd tend to assume that if this function was passed a null that that was a mistake and an error should be thrown.

    Yes, it depends on whether I'm in programmer mode or mathematical-pedantic-dickweed-do-what-the-name-says mode. I only use an Integer when there's a reason to do so...either null is a possibility, or I'm using it in a Map or something.



  • @boomzilla said:

    @Mcoder said:
    And, of corse, for negatives:

    So, can you please cite a negative number and its logarithm, base 2? I am eager to learn this new mathematics. Do you also have anything on division by zero?


    -1 and i*pi/log(2)

    What's that? You wanted to test for integer powers of two?

    Crap.



  • @Scarlet Manuka said:

    Or don't try to do it in a bit-twiddling one-liner which is easy to get subtly wrong. That's an option too.

    Eh, I'm usually opposed to overly "clever" code, but in this case I think it's the best solution, if properly commented. The other options are all pretty gnarly. The best alternative I could think up is:

    return (n > 1) && (Integer.highestOneBit(n) == Integer.lowestOneBit(n));


    I guess it's slightly less arcane-looking. It's slower, but unless you're doing billions of calls it probably won't matter.



  • @boomzilla said:

    Yes, it depends on whether I'm in programmer mode or mathematical-pedantic-dickweed-do-what-the-name-says mode. I only use an Integer when there's a reason to do so...either null is a possibility, or I'm using it in a Map or something.

    I use Integers a lot, but that's because I find myself using collections and generics a lot. If it's a local variable or an instance variable, I'd probably use int unless there's a good reason not to. For functions like this, an int is probably better because it pushes the error into the calling code (I don't find the performance argument persuasive); I don't see any reason this function should ever take a null. Regardless, having null checks all over the place is one of the reasons I hate Java.



  • @morbiuswilters said:

    Eh, I'm usually opposed to overly "clever" code, but in this case I think it's the best solution, if properly commented. The other options are all pretty gnarly. The best alternative I could think up is:

    return (n > 1) && (Integer.highestOneBit(n) == Integer.lowestOneBit(n));


    I guess it's slightly less arcane-looking. It's slower, but unless you're doing billions of calls it probably won't matter.
    return n && n == (n & -n);


  • @havokk said:

    I am disappointed that no-one has solved this using regular expressions.

    Baby steps...

    private Boolean isModulo2(Integer value) {
    Regex r = new Regex(".*[24680]+$");
    return "true".Equals(r.Replace(value.ToString(), "true"));
    }


  • @alegr said:

    @morbiuswilters said:

    Eh, I'm usually opposed to overly "clever" code, but in this case I think it's the best solution, if properly commented. The other options are all pretty gnarly. The best alternative I could think up is:

    return (n > 1) && (Integer.highestOneBit(n) == Integer.lowestOneBit(n));


    I guess it's slightly less arcane-looking. It's slower, but unless you're doing billions of calls it probably won't matter.
    return n && n == (n & -n);

    Very nice! For Java you'd have to change it to:

    return (n > 0) && n == (n & -n);

  • ♿ (Parody)

    @Speakerphone Dude said:

    @havokk said:

    I am disappointed that no-one has solved this using regular expressions.

    Baby steps...

    private Boolean isModulo2(Integer value) {
    Regex r = new Regex(".*[24680]+$");
    return "true".Equals(r.Replace(value.ToString(), "true"));
    }

    Seems like it should be done in perl:

    sub isPowerOfTwo{
    	$_ = 1 x shift(@_);
    	my $p2;
    	while( /^(11+?)\1+$/ ) {
    		$p2 .= length $1;
    		$_= 1 x ( length() / length $1 )
    	}
    	$p2 .= length;
    	return 0 != $p2 =~ /^2+$/;
    }
    

    I'm not much of a perl hacker, but I'm sure someone here knows how to obfuscate condense this. It only handles numbers greater than 1, since it relies on prime factorization, but adding special handlers just...feels dirty.



  • @boomzilla said:

    but adding special handlers just...feels dirty.

    Yeah, because you totally didn't just write a power-of-two check using string manipulation.



  • In Java I always write this method as:

    return n > 0 && Integer.bitCount(n) == 1;

    In terms of bit-twiddling tricks, you can't get much clearer than that.



  • @arotenbe said:

    In Java I always write this method as:

    How often do you have to write this same method?

    @arotenbe said:

    return n > 0 && Integer.bitCount(n) == 1;

    In terms of bit-twiddling tricks, you can't get much clearer than that.

    Damn, didn't know there was a bitCount method. Also nice!



  • @havokk said:

    I am disappointed that no-one has solved this using regular expressions.

    public boolean powerOfTwo(int input) {
        return Integer.toBinaryString(input).matches("^10{0,30}$");
    }
    What it's doing: convert it to a string binary representation, and match a leading one followed by at most 30 zeroes.
    This works because Java's toBinaryString() method will trim off leading zeroes. If the integer is negative, there will be 32 characters in the string.



  • @morbiuswilters said:

    How often do you have to write this same method?

    Once per Java project where I need to check whether something is a power of two. =D

    Seriously, I try to use Guava wherever possible, but there's a couple of functions I just end up rewriting over and over again.


Log in to reply