• usitas (unregistered)

    I love how everyone is complaining about negative numbers, when the code is clearly checking the size of an image. I've never seen any images that were less than 1x1...

    I also think that this is not really a WTF as it is clearly readable (nobody here had an issue figuring out what it did), and doesn't perform poorly. Yes, it could be better, but it could be a lot worse.

  • Anon (unregistered) in reply to regeya
    regeya:
    Because it's wrong?

    x & (x-1) is correct.

    That's what I was thinking, too, as long as x > 0.

    I don't know what's wrong with the whippersnappers.

    And I would say that, since the function is called "checkSize", it's a fair assumption that the input to the function will be > 0.

  • flo99 (unregistered)

    The hard way (bit set count must be 1)

    int checkSize(int x) { if(x<2 || x>512) return 0; x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); int c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; return c==1?1:0; }

  • Bitty Tables (unregistered)

    Well it is quite obvious you young'uns have been spoiled by your compilers and your IDEs to the point where you no longer even automatically think in binary. So I'll spell it out for you. A few common powers of two are:

    00000001 00000010 00000100 00001000 00010000

    and so on. Notice that in every case there is one "1" and the rest are zeros. Now your solution is easy. Just sum up the digits. In Perl:

    $X=join ('+', split (//, '00001000')); return (eval "$X+0") eq '1';

  • Patrick (unregistered) in reply to Bryan The K
    Bryan The K:
    There - saved you a few lines of code. Wait, we're getting paid per line of code, aren't we?
    If you get paid per line of code, how much do you get paid for reducing it, even if it does make it more efficient?

    There have been plenty of times that I've cut someone else's code files in half while still adding features, at that rate I'd be paying the company!

  • Harrow (unregistered)

    There's nothing wrong with this code. The problem lies in the comment "Make sure the image is a power of 2." The purpose of the function is obviously "Make sure the image size is acceptable."

    A second comment line might be "Acceptable sizes are powers of two from 2 to 512." but this is not really necessary as it is obvious from the code, once the original comment is debugged properly.

    -Harrow.

  • Insensitive Claude (unregistered)

    asm volatile ("popcnt %0 = 1" : "=%r" (output) : "r" (input));

  • (cs) in reply to Ben
    Ben:
    I would thus argue for:

    return ((x > 0) ? ((x & (x-1)) == 0) : 0);

    Why use a conditional operator when a plain old boolean AND does the same thing? "a && b" is a little more clear and easier to parse than "a ? b : 0".

  • Insensitive Claude (unregistered) in reply to Insensitive Claude
    Insensitive Claude:
    __asm__ __volatile__ ("popcnt %0 = 1" : "=%r" (output) : "r" (input));

    Or rather cleaner on gcc:

    return ( __builtin_popcount (n) == 1 );

  • (cs) in reply to Ouch!
    Ouch!:
    frits:
    Ouch!:
    i == 2^(INT_BITS - 2)
    , you get a value not representable in int, so undefined behaviour. I'd be surprised if any implementation gave something other than INT_MIN then, but it could do anything.
    Uh, 
    i == 2^(INT_BITS - 2);
    = 0x1C in a 32 bit system. That's hardly undefined.
    Firstly, after, not when. Secondly, I used (^) as the exponentiation operator, of course (and anyway, you don't know how INT_BITS is defined, so it might well be undefined behaviour even if I had used (^) as `xor`).

    1. There is no "exponentiation operator" in C.

    2. In C, ints always have defined behavior. All permutations of bits represent some value.

    3. Your postcount of boring nonsense is way too high today. Please refrain from posting until you can add something someone (besides you) wants to read.

  • caper (unregistered)

    Well it is quite obvious you young'uns have been spoiled by your compilers and your IDEs

    Finally, someone who uses a language other than C.

  • (cs)

    Would this work?

    // If x is a power of 2, Log2(x) is a whole number
// Log2(x) = Log(x) / Log(2)
if (Math.Floor(Math.Log(x) / Math.Log(2)) == Math.Log(x) / Math.Log(2))
{
     return true;
}
else
{
     return false;
}
  • Ouch! (unregistered) in reply to frits
    frits:
    Ouch!:
    frits:
    Ouch!:
    i == 2^(INT_BITS - 2)
    , you get a value not representable in int, so undefined behaviour. I'd be surprised if any implementation gave something other than INT_MIN then, but it could do anything.
    Uh, 
    i == 2^(INT_BITS - 2);
    = 0x1C in a 32 bit system. That's hardly undefined.
    Firstly, after, not when. Secondly, I used (^) as the exponentiation operator, of course (and anyway, you don't know how INT_BITS is defined, so it might well be undefined behaviour even if I had used (^) as `xor`).
    1. There is no "exponentiation operator" in C.
    That was pseudocode.
    2. In C, ints always have defined behavior. All permutations of bits represent some value.
    #include <limits.h>

#define INT_BITS (((int)1) << (sizeof(int)*CHAR_BIT + 3))

    And

    C99:
    6.5.7 If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
    3. Your postcount of boring nonsense is way too high today. Please refrain from posting until you can add something someone (besides you) wants to read.
    Your postcount of unfunny jerkiness is way too high this year. Nevertheless, keep on posting if it gives you joy.
  • Mikhail (unregistered)

    Another pretty concise solution, assuming Java is the language in question.

    int checkSize(int x) if (x <= 0) { return 0; } double logBase2OfX = Math.log(x) / Math.log(2); boolean isLogBase2OfXWholeNumber = Math.floor(logBase2OfX) == Math.ceiling(logBase2OfX); return isLogBase2OfXWholeNumber ? 1 : 0; }

  • Mikhail (unregistered)

    Did not notice that someone already proposed my solution, and yes... it works.

  • Pascal (unregistered)

    Hey, John, welcome.

    Next time someone sends in a piece of C, just explain you're not the person to judge if it's a WTF or not.

    The bit-twiddling code to check if a binary number has a single bit set has already been posted, but it is not widely known and a programmer cannot be blamed for not knowing it. There is no reason to assume that the function is not pre-C99 C with the information given, and anyway, habits simply die hard. There is no reason to assume that the argument is not bounded, although this should be better documented.

    This is an absolute non-WTF, although the comment with the sqrt function was pretty funny.

  • RandomUser423686 (unregistered) in reply to Ouch!
    Ouch!:
    RandomUser423686:
    Or was it just my elementary school teachers who got all strict about "you only say 'and' in a number where you would put the decimal separator, and your answer is wrong if you mess it up," way back when?
    No, that seems to be rather common in the USA. So much so that many (a few handful at least) merrickuns can't cope with the fact that the rest of the English speaking world has different conventions.
    Okay. Just another example of dialectal English "rules" perpetuating themselves, despite their lack of utility if not uniformly adopted. Probably qualifies them to be classed as viral memes, or at least similar.
  • Pascal (unregistered) in reply to Mikhail

    Floating-point logarithm and division for a function that probably fails to detect at least a couple of powers of two (more depending on the FPU's rounding mode)? Impressive!

  • fjf (unregistered) in reply to Patrick
    Patrick:
    Bryan The K:
    There - saved you a few lines of code. Wait, we're getting paid per line of code, aren't we?
    If you get paid per line of code, how much do you get paid for reducing it, even if it does make it more efficient?

    There have been plenty of times that I've cut someone else's code files in half while still adding features, at that rate I'd be paying the company!

    If I'd ever accept payment by LOC, I'd only do so with a negative factor (when working on existing code, not writing new code, obviously).

  • Anon (unregistered) in reply to Bitty Tables
    Bitty Tables:
    Well it is quite obvious you young'uns have been spoiled by your compilers and your IDEs to the point where you no longer even automatically think in binary. So I'll spell it out for you. A few common powers of two are:

    00000001 00000010 00000100 00001000 00010000

    and so on. Notice that in every case there is one "1" and the rest are zeros. Now your solution is easy. Just sum up the digits. In Perl:

    $X=join ('+', split (//, '00001000')); return (eval "$X+0") eq '1';

    And to add, a few common powers of 2 minus 1:

    00000000 00000001 00000011 00000111 00001111

    This is why x & (x-1) == 0 is true when x is a power of 2.

  • Massive Debt (unregistered) in reply to Daid
    Daid:
    C has no boolean type.

    No, C has the same boolean type as Assembler. Namely, they branch on zero, or execute the IF-block on non-zero.

  • Corey (unregistered) 
    sub check_size {
    return (scalar(grep { $_ } split //, unpack("B32", pack("N", $_))) == 1);
}

    ...what? why is everyone trying to set me on fire?

  • Buddy (unregistered)

    No bitwise operators, should be safe for all integer representations including BCD! In two's complement systems, smart compilers can substitute & 1 for % 2 and >>= 1 for /= 2. Disadvantage: runs in O(log(x)) as opposed to O(1).

    bool is_power_of_two(unsigned x)
{
    if (x)
    {
        while (!(x % 2))
            x /= 2;
    }

    return x == 1;
}
  • bitrot (unregistered)

    Google for 'bit twiddling hacks' for some incredible bit twiddles such as bitwise reversing a byte in only seven logical/multiply operations. It correctly lists the solution for 'check if unsigned int is a power of two' (and which checks for 0) as:

    f = v && !(v & (v - 1));

    But by looking deeper you can get a truly overengineered solution by, for example, counting the set bits and comparing the result to 1:

    static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

bool result = ((c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]) == 1); 

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
  • Thg (unregistered) in reply to frits
    frits:
    Ouch!:
    frits:
    Uh, 
    i == 2^(INT_BITS - 2);
    = 0x1C in a 32 bit system. That's hardly undefined.
    Firstly, after, not when. Secondly, I used (^) as the exponentiation operator, of course (and anyway, you don't know how INT_BITS is defined, so it might well be undefined behaviour even if I had used (^) as `xor`).

    1. There is no "exponentiation operator" in C.

    2. In C, ints always have defined behavior. All permutations of bits represent some value.

    3. Your postcount of boring nonsense is way too high today. Please refrain from posting until you can add something someone (besides you) wants to read.

    1. (fully understanding that I may be a hypocrite for saying so) razzing people for simple syntax makes you a troll.

    2. Most of that boring nonsense came from a "sparring match" that I started (and enjoyed). So you didn't even razz all the right people.

    (the power of 'true' must be powerful indeed!)

  • Mikhail (unregistered) in reply to Pascal

    Agree with your comments.

    The solution will not work from time to time, hence not a solution at all. Was just looking at a different from various bit-twiddling approaches everyone posted.

  • Squee (unregistered)

    While embedded systems has been mentioned (including with image sizes), this code is perfectly acceptable for shader GPU code, such as HLSL, where A) You don't have bitshifts (HUGE pain for me sometimes) B) Loops are to be avoided unless unrollable (which this would be, but whatever) and C) Instruction count matters. It doesn't even have to be for image size checking, could be for many things of power of 2 with range checking there. Of course, there is a bool type in shader languages, but that's hardly a big WTF.

  • J2ME Peon (unregistered) in reply to Bernard Mergendeiler
    Bernard Mergendeiler:
    Stopping at 512 might be a good idea. Wouldn't want the code to be two powerful.

    You jest, but you might actually be right. I'm guessing this is a check to see if they're being passed a texture whose dimensions are within allowed limits on a machine that can't cope with textures larger than 512x512.

    Sure, it's inelegant and named wrong, but if it's being used for this, it isn't that WTFy.

  • Thg (unregistered) in reply to Insensitive Claude
    Insensitive Claude:
    __asm__ __volatile__ ("popcnt %0 = 1" : "=%r" (output) : "r" (input));

    now my eyes are bleeding!

  • sino (unregistered) in reply to Anonymous
    Anonymous:
    Another new author? Great! Welcome, John.
    I find it disturbingly telling that you called him an author, rather than an editor... :S
  • usitas (unregistered) in reply to sino
    sino:
    Anonymous:
    Another new author? Great! Welcome, John.
    I find it disturbingly telling that you called him an author, rather than an editor... :S

    Maybe he was implying that John made it up.

  • (cs) in reply to Thg

    a. My point was that there is no single operator for exponentiation. It takes several multiplications, or in the special case of 2, one bit shift.

    b. Razzing people for simple syntax does not make one a troll, per se. It happens all the time on this site. That being said, I'm not claiming I am not a troll.

    1. Yes. that was a boring sword fight, but that wasn't the only boring exchange "Ouch!" was involved in today. BTW- ironically, I'm now adding to the tedium.
  • RandomUser423686 (unregistered) in reply to sino
    sino:
    Anonymous:
    Another new author? Great! Welcome, John.
    I find it disturbingly telling that you called him an author, rather than an editor... :S
    Well, we already know that, by and large, the articles here are based-on-reality fiction at best. BOCTAOE
  • Will (unregistered)

    bool CheckSize (int n) { int k; for (int i = 0; i < ∞; i++) { k = 1; for (int j = 0; j < i; j++) k *= 2; if (k == n) return true; } return false; }

  • ==andrey== (unregistered)

    x & (x-1) came from an ACM paper in the 50s or 60s, the title of which I forgot. There's a high chance it's cited on the wikipedia link containing x&(x-1)

  • Quirkafleeg (unregistered) in reply to RandomUser423686
    RandomUser423686:
    Markp:
    ... "sixty-seven million, one hundred and eight thousand, eight hundred sixty-four."
    The context made it more than clear what was meant, but did anyone else read this the intended way first, and then cynically as 67000100.8864?
    It could be any of these:

    67000000 108000 800 64

    67108000 800 64

    67000000 108800 64

    67108800 64

    It would not be 671008864 due to a missing ‘and’, though the punctuation suggests that this is what it is actually intended to be.

    Or was it just my elementary school teachers who got all strict about "you only say 'and' in a number where you would put the decimal separator, and your answer is wrong if you mess it up," way back when?
    Yes – strictly wrong. Yours would be “sixty-seven million, one hundred point eight eight six four”.
  • Way2trivial (unregistered)

    convert the number to binary, then convert that to astring

    parse the string leftmost must equal 1, all trailing digits must equal zero

  • Bowie (unregistered)

    Powers of 2 actually used to be a drinking game when I was at U of A.

    ...Yeah, sad, I know.

    But at least I could drink 99% of those sons of bitches under the table. :)

  • Nano J. Gator (unregistered)

    I wrote a function almost exactly like this once. It was for dealing with textures in a video game environment. There were only a handful of certain legal sizes they could be, up to 1024. This code snippet could easily be a "is this resolution legal?" function, not a "is this a power of 2?" function.

    This isn't a 'fail' unless we know what the context is.

  • user unknown (unregistered)

    That code may be C, Java, Lua or something else. Even if it is C, we don't know how big int is on the plattform.

    Without more context it isn't a WTF, I agree. Maybe there is an outer restriction for the images to not be bigger than 1023.

    Va bene!

  • nasch (unregistered) in reply to Knux2
    Knux2:
    Psssh...not very Enterprise-y. This is how he SHOULD have written it (in Java):

    Please. Besides the obvious lack of XML that has already been pointed out, you could easily make that more enterprise-y with an enum! ;-)

  • mike (unregistered) in reply to Pascal
    Pascal:
    The bit-twiddling code to check if a binary number has a single bit set has already been posted, but it is not widely known and a programmer cannot be blamed for not knowing it.

    Really? In this day and age? Just google "C ispowerof2". Heck, click "I'm feeling lucky" there and you get your answer.

    And seriously, if you're a programmer, you should learn how to count in binary.

  • smxlong (unregistered)

    Suppose you're handed a spec and asked to check if the piece of code conforms to the spec. The spec says, "The size of the image shall be 2, 4, 8, 16, 32, 64, 128, 256, or 512. Other sizes are invalid."

    Given this spec, how hard is it to verify that the posted code implements the spec correctly? How hard is it to verify that people's posted alternatives implement it correctly?

    You people are freaks.

  • (cs)

    TRWTF would have been if he checked for NEGATIVE powers of 2.

  • (cs) in reply to Sylver
    Sylver:
    TRWTF here is that this code ends up on thewailywtf.com in the first place.

    It's a short piece of code that works. It's not elegant, bordering on clumsy, but hey, it works, and it is easy to understand. That's more than can be said of most of the answers given in the comments.

    How about some real WTF? Gosh, I miss the brillant days of Paula.

    Yeah, it's piss-poor as a WTF.

    It works for powers up to 2^9, and probably it was meant to work on a small subset of predictable inputs (that "image size" in the comment should ring a bell, if it's not just an anonymization. It also would explain why certain inputs such as 1 or negatives or 1024 wouldn't be accepted: predictable input set). As for the "lack of boolean" the submitter probably wasn't aware that certain bracket-and-semicolon languages don't have a built-in boolean type.

    If anything, this could be shortened to:

    int checkSize(int x) { return (x == 2 || x == 4 || x == 8 || x == 16 || x == 32 || x == 64 || x == 128 || x == 256 || x == 512); }

    Did I mention it's a piss-poor WTF?

    Addendum (2010-05-13 03:32):

    Sylver:
    TRWTF here is that this code ends up on thewailywtf.com in the first place.

    It's a short piece of code that works. It's not elegant, bordering on clumsy, but hey, it works, and it is easy to understand. That's more than can be said of most of the answers given in the comments.

    How about some real WTF? Gosh, I miss the brillant days of Paula.

    Yeah, it's piss-poor as a WTF.

    It works for powers up to 2^9, and probably it was meant to work on a small subset of predictable inputs (that "image size" in the comment should ring a bell, if it's not just an anonymization. It also would explain why certain inputs such as 1 or negatives or 1024 wouldn't be accepted: predictable input set). As for the "lack of boolean" the submitter probably wasn't aware that certain bracket-and-semicolon languages don't have a built-in boolean type.

    If anything, this could be shortened to:

    int checkSize(int x) { return (x == 2 || x == 4 || x == 8 || x == 16 || x == 32 || x == 64 || x == 128 || x == 256 || x == 512); }

    Did I mention it's a piss-poor WTF?

    Maurits:
    Tsk, tsk. Think of the performance hit of all those comparisons!

    Short-circuit evaluation is your friend <3

  • Jimmy Jones (unregistered) in reply to AnOldHacker
    AnOldHacker:
    You guys are amazing. Suppose x = 0. What do you get for x & (x - 1), hmmm?

    This could get bloody...pass the popcorn.

  • Jimmy Jones (unregistered) in reply to mike

    [quote user="mike"][quote user="Pascal"] Really? In this day and age? Just google "C ispowerof2". Heck, click "I'm feeling lucky" there and you get your answer. [/quote]

    Umm...all these posts and we don't know if the spec said "is power of two".

    Maybe there was a list of "legal values", and "1" wasn't in it and neither were any numbers higher than 512.

  • Jimmy Jones (unregistered) in reply to heretic

    [quote user="heretic"][quote user="anon"][quote user="java.lang.Chris;"][quote user="Ocson"]With regard to the lack of boolean, this could have been written in C.[/quote] [quote user="Daid"]C has no boolean type.[/quote]

    // party like it's c99

    #include <stdbool.h> [/quote]

    Seriously. C99 was ratified eleven years ago. Why do people pretend it doesn't exist?[/quote]

    Because Microsoft support for the C99 standard is less than stellar?[/quote]

    They also don't do ALGOL, COBOL, FORTRAN, Pascal or any other 1970's programming languages. Your point is...?

    [quote user="heretic"] For all of Linux's distinct advantages (open source, GCC, etc.) as a development platform, I know of precious few businesses actually doing development on it (and even fewer universities which teach using the open source development tool-chain).[quote]

    There's something as good as Visual C++ for Linux? GCC produces code which is as small/fast as the Microsoft compiler?

    [quote]Remember it is all about vendor lock-in.[/quote]

    I develop my code using Visual C++ Express (a free download from Microsoft). When I need a Linux build I compile it on the Linux machine via telnet from my Windows desktop.

    Oh yeah, that's total lock-in.

  • Jimmy Jones (unregistered) in reply to C4I_Officer
    C4I_Officer:
    Did I mention it's a piss-poor WTF?

    Well, after all these years it's hard to keep raising the bar every single day.

  • petermount (unregistered)

    In Java, it would be a power of 2 if only one bit is set...

    int checkSize( int x ) {
    return Integer.bitCount( x ) == 1;
}

Leave a comment on “The Power of True”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article