Fight the Powah

morbiuswilters

@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.

It only took 5,000 times longer and had a peak memory consumption of 720MB. As part of an optional $10,000 service pack we'll use a pre-compiled regex. Now our algorithm's worthy of the appellation "Java".

Barbaz

@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.

I would like to point out that all versions are equally readable as long as they are enclosed in

private Boolean isPowerOfTwo(Integer value) {
    ...
}

If you want to argue now that it is not obvious whether they are correct, just look into the unit tests.

token_woman

public static boolean wank(integer theInt)

{

return theInt == 1 || Math.mod(theInt,2) != 1 && wank(theInt/2);

}

Just some recursive wanking

boomzilla

@Mr. DOS said:

@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.

Sometimes I just can't handle it when people try to strangle my sense of creativity by insisting that there's only one way to do it. At least it wasn't poetry.

dhromed

@token_woman said:

theInt

People who write these kind of variable names in earnest should probably have their privates run through with a potato peeler.

token_woman

@dhromed said:

@token_woman said:
theInt

People who write these kind of variable names in earnest should probably have their privates run through with a potato peeler.

Not that that wouldn't be fun, but in the kind of example I was writing (a generic function for doing something with an integer completely out of any context), what better name would you suggest?

token_woman

D'oh!!! Just got it. "Integer theInt". Yeah that would be peeler-worthy indeed in a language that had two different types, int and Integer.

However, the language I work in (but not for much longer, Hurrah!) is not actually Java but a subset (an idiotic subset) which has no Integer class and its int-like type is called "integer".

That sounds so far-fetched I don't actually expect anyone to believe it, but it's true. So ... well .... ner.

Edit: oh, and it's case-insensitive so "integer" / "Integer" OK. No, I don't expect you to believe that either.

dhromed

I'll post when I'm feeling less bewildered.

MrDOS

@token_woman said:

Not that that wouldn't be fun, but in the kind of example I was writing (a generic function for doing something with an integer completely out of any context), what better name would you suggest?

n.

That single letter implies that

the function is not just a generic function, but a generic math function,
the value of the argument is a constant through the operation of the function (based on the mathematical implications of a variable being named n), and
the result of the function is directly affected by the argument (although that should apply to any static function)

Then again, most of the java.lang.Math methods use a/b so I don't know that anyone outside of this forum really cares about this sort of thing.

morbiuswilters

@Mr. DOS said:

n.
That single letter implies that

the function is not just a generic function, but a generic math function,

the value of the argument is a constant through the operation of the function (based on the mathematical implications of a variable being named n), and

the result of the function is directly affected by the argument (although that should apply to any static function)

Then again, most of the java.lang.Math methods use a/b so I don't know that anyone outside of this forum really cares about this sort of thing.

Yeah, I don't think anyone actually follows that idiom. Certainly not enough to make any kind of assumptions based on a parameter being named or not being named "n". So nobody inside this forum cares about it, either.

boomzilla

@morbiuswilters said:

@Mr. DOS said:
n.
That single letter implies that

the function is not just a generic function, but a generic math function,

the value of the argument is a constant through the operation of the function (based on the mathematical implications of a variable being named n), and

the result of the function is directly affected by the argument (although that should apply to any static function)

Then again, most of the java.lang.Math methods use a/b so I don't know that anyone outside of this forum really cares about this sort of thing.

Yeah, I don't think anyone actually follows that idiom. Certainly not enough to make any kind of assumptions based on a parameter being named or not being named "n". So nobody inside this forum cares about it, either.

And anyways, why use "n"? In math, it's typically used for describing cardinality. If you're dealing with an arbitrary function with a parameter, it's almost always written as f(x).

MrDOS

@boomzilla said:

And anyways, why use "n"? In math, it's typically used for describing cardinality. If you're dealing with an arbitrary function with a parameter, it's almost always written as f(x).

Er. Yes. x. Not n. That's rather embarassing.

RedFeather

Cast it to a floating point, then extract the mantissa and see if it's zero. [/troll]

boomzilla

@RedFeather said:

Cast it to a floating point, then extract the mantissa and see if it's zero. [/troll]

Of course!

#include <ieee754.h>
int isPowerOfTwo( int value ){
	union ieee754_double d;
	d.d = (double) value;
	return !(d.ieee.mantissa0  | d.ieee.mantissa1);
}

nosliwmas

The best way with a single line is to check if the log (in base 2) of the number is an integer.

morbiuswilters

@nosliwmas said:

The best way with a single line is to check if the log (in base 2) of the number is an integer.

Older Java only had natural logarithms, so you had to do log(x) / log(2). Newer Java does let you use an arbitrary base, but with the old and new methods you still end up with a double. I'm wary of fucking around with floating point when the bitwise check is faster and seems safer.

MrDOS

@morbiuswilters said:

I'm wary of fucking around with floating point when the bitwise check is faster and seems safer.

That was my line of thought, too:

public static boolean isPowerOfTwo(int x)
{
    double exponent = log(x) / log(2);
    return (exponent == (double) ((int) exponent));
}

but the possibility of false-positives (and positive-falses) caused by floating-point imprecision seemed too high.

boomzilla

@morbiuswilters said:

@nosliwmas said:
The best way with a single line is to check if the log (in base 2) of the number is an integer.

Older Java only had natural logarithms, so you had to do log(x) / log(2). Newer Java does let you use an arbitrary base, but with the old and new methods you still end up with a double. I'm wary of fucking around with floating point when the bitwise check is faster and seems safer.

All I see (as far as bases other than e) is log10(). A quick test shows that log(x) / log(2) works for all integer powers of 2 (and integer powers of 2 minus 1).

morbiuswilters

@Mr. DOS said:

@morbiuswilters said:
I'm wary of fucking around with floating point when the bitwise check is faster and seems safer.
That was my line of thought, too:
public static boolean isPowerOfTwo(int x)
{
    double exponent = log(x) / log(2);
    return (exponent == (double) ((int) exponent));
}
but the possibility of false-positives (and positive-falses) caused by floating-point imprecision seemed too high.

It's also about 39 times slower than the fastest method (the Integer.bitCount one from arotenbe).

morbiuswilters

@boomzilla said:

All I see (as far as bases other than e) is log10().

Dammit, I thought I saw one.

@boomzilla said:

A quick test shows that log(x) / log(2) works for all integer powers of 2 (and integer powers of 2 minus 1).

Fair enough. It's still second slowest (after the regex).

MrDOS

@morbiuswilters said:

It's also about 39 times slower than the fastest method (the Integer.bitCount one from arotenbe).

That surprises me -- I thought for sure one of the bithacks would've been the fastest. How much faster is bitCount?

boomzilla

@morbiuswilters said:

@boomzilla said:
A quick test shows that log(x) / log(2) works for all integer powers of 2 (and integer powers of 2 minus 1).

Fair enough. It's still second slowest (after the regex).

Hmmm......that sounds like a ~~troll~~ challenge.

morbiuswilters

@Mr. DOS said:

@morbiuswilters said:
It's also about 39 times slower than the fastest method (the Integer.bitCount one from arotenbe).
That surprises me -- I thought for sure one of the bithacks would've been the fastest. How much faster is bitCount?

I did i = 0; i < Integer.MAX_VALUE. Did the timing using Date.getTime() before and after the loop. Ran multiple tests to confirm consistency.

Both bithacks	85ms
log(n)/log(2)	2500ms
Integer.highestOneBit(n) == Integer.lowestOneBit(n)	255ms
bitCount	65ms
regex	little over 15 minutes

Man, I really should get back to work..

antiquarian

@token_woman said:

D'oh!!! Just got it. "Integer theInt". Yeah that would be peeler-worthy indeed in a language that had two different types, int and Integer.

However, the language I work in (but not for much longer, Hurrah!) is not actually Java but a subset (an idiotic subset) which has no Integer class and its int-like type is called "integer".

That sounds so far-fetched I don't actually expect anyone to believe it, but it's true. So ... well .... ner.

Edit: oh, and it's case-insensitive so "integer" / "Integer" OK. No, I don't expect you to believe that either.

What language is it? Ada's case-insenstive and has an int-like type called integer.

morbiuswilters

@PedanticCurmudgeon said:

@token_woman said:
D'oh!!! Just got it. "Integer theInt". Yeah that would be peeler-worthy indeed in a language that had two different types, int and Integer.

However, the language I work in (but not for much longer, Hurrah!) is not actually Java but a subset (an idiotic subset) which has no Integer class and its int-like type is called "integer".

That sounds so far-fetched I don't actually expect anyone to believe it, but it's true. So ... well .... ner.

Edit: oh, and it's case-insensitive so "integer" / "Integer" OK. No, I don't expect you to believe that either.
What language is it? Ada's case-insenstive and has an int-like type called integer.

It seems like she's saying it's a subset of Java, so likely some awful, proprietary language that gets run through a preprocessor and turned into Java.

RichP

Because someone has to do it:

private Boolean isPowerOfTwo(Integer value) {

   if (value ==1) {

       return true;
   } else if (value ==2) {
       return true;
   } else if (value ==2) {
       return true;
   } else if (value ==4) {
       return true;
   } else if (value ==8) {
       return true;
   } else if (value ==18) {
       return true;
   } else if (value ==32) {
       return true;
   } else if (value ==64) {
       return true;
   } else if (value ==128) {
       return true;
   } else if (value ==256) {
       return true;
   } else {
   // Brilliant!
       return FILE_NOT_FOUND;
       }

}

dhromed

I'm especially fond of this bit.

@RichP said:

} else if (value ==2) {
       return true;
   } else if (value ==2) {
       return true;
   }

lol i said bit

morbiuswilters

@dhromed said:

I'm especially fond of this bit.
@RichP said:
} else if (value ==2) {
       return true;
   } else if (value ==2) {
       return true;
   }

lol i said bit

Cosmic rays might've changed the value in between the checks. You can never be too sure..

Scarlet_Manuka

@dhromed said:

I'm especially fond of this bit.

What, you like that better than the progression from 8 to [b]18[/b] to 32?

fyjham

In the interest of losing in performance to regex (example is in C#):

        public static bool CheckPowerOfTwo(int value)
        {
            checked
            {
                try 
                {
                    for (int i=1; i < Int32.MaxValue; i++)
                    {
                        int powerOfTwo = 1;
                        for (int j = 0; j < i; j++)
                        {
                            powerOfTwo = powerOfTwo * 2;
                            if (powerOfTwo == value) return true;
                        }
                    }
                    return false;
                } catch (OverflowException) { return false; }
            }
        }

Didn't let it play out long-term, but it took 20 seconds to do the first 4000, so in theory it should take a few months to do all integers...

token_woman

@morbiuswilters said:

@PedanticCurmudgeon said:
@token_woman said:
D'oh!!! Just got it. "Integer theInt". Yeah that would be peeler-worthy indeed in a language that had two different types, int and Integer.

However, the language I work in (but not for much longer, Hurrah!) is not actually Java but a subset (an idiotic subset) which has no Integer class and its int-like type is called "integer".

That sounds so far-fetched I don't actually expect anyone to believe it, but it's true. So ... well .... ner.

Edit: oh, and it's case-insensitive so "integer" / "Integer" OK. No, I don't expect you to believe that either.
What language is it? Ada's case-insenstive and has an int-like type called integer.

It seems like she's saying it's a subset of Java, so likely some awful, proprietary language that gets run through a preprocessor and turned into Java.

Wish it was Ada - at least that has a kind of old-school patriotic chic. Sadly though, morbius is spot on.

OperatorBastardusInf

WORNG. I have a much better regex.

sub isPowerOfTwo {
  ('1' x $_[0]) =~ /^1(|1((?1))\2)$/);
}

RedFeather

@boomzilla said:

#include 
int isPowerOfTwo( int value ){
	union ieee754_double d;
	d.d = (double) value;
	return !(d.ieee.mantissa0  | d.ieee.mantissa1);
}

No, that's far too readable. I had in mind something like:

bool isPowerOfTwo(float value)
{
	return !(*(int *) &value << sizeof(float)*8 - FLT_MANT_DIG + 1);
}

Because really, why bother doing it in C++ if you're not going to have incomprehensible pointer idiocy? (This cheats a bit on the one-line rule, in that part of the functionality is included in the signature, which does the actual casting into a float).

ETA: Also, this only works if floats and ints are exactly the same size

boomzilla

@RedFeather said:

Because really, why bother doing it in C++ if you're not going to have incomprehensible pointer idiocy? (This cheats a bit on the one-line rule, in that part of the functionality is included in the signature, which does the actual casting into a float).

That's fair. It was really just a first pass, without any attempt at obfuscation or cleverness. However, using a float loses too much precision to handle the full range of ints. You really need to use a double.

antiquarian

@token_woman said:

@morbiuswilters said:
@PedanticCurmudgeon said:
@token_woman said:
D'oh!!! Just got it. "Integer theInt". Yeah that would be peeler-worthy indeed in a language that had two different types, int and Integer.

However, the language I work in (but not for much longer, Hurrah!) is not actually Java but a subset (an idiotic subset) which has no Integer class and its int-like type is called "integer".

That sounds so far-fetched I don't actually expect anyone to believe it, but it's true. So ... well .... ner.

Edit: oh, and it's case-insensitive so "integer" / "Integer" OK. No, I don't expect you to believe that either.
What language is it? Ada's case-insenstive and has an int-like type called integer.

It seems like she's saying it's a subset of Java, so likely some awful, proprietary language that gets run through a preprocessor and turned into Java.

Wish it was Ada - at least that has a kind of old-school patriotic chic. Sadly though, morbius is spot on.

Sounds like a front-page-worthy abomination. And I thought MUMPS was bad...

RedFeather

@boomzilla said:

Using a float loses too much precision to handle the full range of ints. You really need to use a double.

Out of all the problems with that function, that's the one that bothers you?

Obfuscator

+1 On that "not null" should be the default, as should "final". If you don't want to change languages, you should check out the JetBrains tool and compiler extensions for @NotNull and @Nullable annotations. They add runtime assertions and warn while compiling in situations where you risk NPEs. They tried to get this into the lang for years, but Sun rejected by basically saying "Nice idea but it belongs in the lang, so we cannot accept the current form. We also decided to not include it in the lang". Cue 10 years, still no change. Check out the upcoming JetBrains lang "Kotlin" for some nice ideas on these fronts.

arotenbe

I think the reason the bitCount one is fastest is that the JIT compiler is actually optimizing the call to bitCount into a machine instruction. When I tried debugging a piece of code that uses bitCount, the debugger refused to step into it (even though I've got the source for the software implementation of bitCount in the JDK). I couldn't find much information on this, but here's something.

morbiuswilters

@Obfuscator said:

+1 On that "not null" should be the default, as should "final". If you don't want to change languages, you should check out the JetBrains tool and compiler extensions for @NotNull and @Nullable annotations. They add runtime assertions and warn while compiling in situations where you risk NPEs. They tried to get this into the lang for years, but Sun rejected by basically saying "Nice idea but it belongs in the lang, so we cannot accept the current form. We also decided to not include it in the lang". Cue 10 years, still no change. Check out the upcoming JetBrains lang "Kotlin" for some nice ideas on these fronts.

Hmm.. fascinating. I'll have to check that out. Thanks for the tip!

morbiuswilters

@arotenbe said:

I think the reason the bitCount one is fastest is that the JIT compiler is actually optimizing the call to bitCount into a machine instruction. When I tried debugging a piece of code that uses bitCount, the debugger refused to step into it (even though I've got the source for the software implementation of bitCount in the JDK). I couldn't find much information on this, but here's something.

Ah, that bug says x86 as a popcnt instruction, so I bet that's what HotSpot is using. Thanks for looking into it!