• (nodebb)

    (1 << n ) - 1

  • (nodebb)

    Still, the return true is going to cast a boolean to a DWORD which because this is clearly WinAPI code, I'm sure it's going to do something weird like actually return 0

    For shame, Remy. DWORD is just an alias for uint32, and the consequence of a cast from bool to an integer type is well-defined by the C++ standards: false becomes zero, true becomes one.

    The other WTF that you missed is the name of the class: CBitOps. Either this is a namespace masquerading as a class (all methods static) or it requires an instance to do something non-instancey. Both are serious structural WTFs.

    I'd also describe the if() on the number of bits being an attempt at premature optimisation rather than input validation, since the return would be 1 all the same if the if() was removed.

  • (nodebb) in reply to TheCPUWizard

    (1 << n ) - 1

    For n strictly less than the number of bits in a DWORD, of course, since otherwise the nasal demons of UB bite you.

  • Sole Purpose Of Visit (unregistered) in reply to Steve_The_Cynic

    Well, yes, but it's the native way of doing the job in C. No pointless call-outs to a library function.

    And also, it makes it more obvious that you need to take care of the upper bound for n. (I have no idea what the library function would do.) A nice easy constant using sizeof(DWORD), and you've got everything neatly right in front of you.

    Of course, what possible purpose that "everything" could conceivably serve is left as an exercise for the reader.

  • doubtingposter (unregistered)

    Not only is this dumb, it doesn't do what is described because the result is off by one. But it's possible the description was wrong and this describes the number of values you can store in a given amount of bits, not its actual value.

  • Meeeee (unregistered)

    The presented code is a lot of WTFs, but the suggestion to use floating point arithmetics (pow) also is.

  • (nodebb)

    Every code snippet in any C style language has the for loop incrementor clause with ++ after the variable: i++. This is definitely a micro optimization but ++i is a bit faster because it doesn't have load the before value after calculating and storing the incremented value.

    Addendum 2021-02-25 08:10: PS. This has nothing to do with the WTF in the story, of course.

  • (nodebb) in reply to Steve_The_Cynic

    @Steve -- I have an entire collections of nasal-demons that I have collected over the years... Feel free to come visit... Admission is free, but the exit price is your soul.

  • my name is missing (unregistered)

    The Wrong BitTwiddler is the one villain even Batman could not deal with.

  • Flips (unregistered) 
    why not return 0 in that case?

    Because you can't put a zero in zero bits of storage, you silly goose =)

  • Thomas J. (unregistered) in reply to Meeeee

    The correct function to call (on all machines with power-of-2 floating point[1]) is scalb like this:

    return scalb(1.0, (double)wNrOfBits);

    [1] I haven't gone through the mental gymnastics if this would also work on the IBM S/360 and later which used power-of-16 exponents in their FPU

  • Anonymous') OR 1=1; DROP TABLE wtf; -- (unregistered) in reply to Mr. TA

    For class types that overload operator++, that's a valid argument. For primitive types, it's 100% wrong, the compiler generates the exact same assembly for i++ and ++i. Which one to use is purely a stylistic choice.

  • (nodebb) in reply to Anonymous') OR 1=1; DROP TABLE wtf; --

    Re: ++i vs. i++ That is true, unless you are also extracting the value of the increment/decrement.

    t = ++i;

    vs.

    t = i++;

    But without the value extraction, the compiler and optimizer generate the same code these days. In the increment of a for loop, it will generally be the same, but I still like ++i more often anyway, BYMMV.

  • mmarsh (unregistered)

    ~( (~0) << n )

  • Scott (unregistered)

    I don't know C++, so maybe DWORD is always non-negative. ..

  • DanK (unregistered) in reply to Mr. TA

    When you see ++i in C code, you know that it was written by a C++ programmer.

  • Anonymous') OR 1=1; DROP TABLE wtf; -- (unregistered) in reply to Nutster

    @Nutster: Yes, I should have clarified that I was referring to the case when the return value is discarded, like in a typical for loop increment expression.

    @Scott: DWORD is always unsigned (it's a standard Win32 type), so the overflow behavior is well-defined: if the input exceeds 32, then the output of CBitOps::BitPower() will be 0. Conversely if it were using a signed integer type, then the overflow behavior would be undefined. (A bit shift implementation of (1<<wNrOfBits) would have undefined behavior for both signed and unsigned types.)

  • J.G.Harston (unregistered) in reply to Steve_The_Cynic

    Yeah, that's gonna overflow if eg n=32 and sizeof=32. Pretend I said 16, (1<<16)-1 gets you 1<<16 gets you 65536 which is too big before you can get to the -1. You need something like (1<<(n-1)-1)*2+1 or something, with range checks.

  • Smithers (unregistered)

    Equally equally inescapable are the number of ways to write simple articles wrong...

    You or I might reach for our language's pow function

    You might; I prefer integer solutions to integer problems.

    The suggestion that this is finding the largest value that can be stored in some number of bits is at least only one off - this calculates the number of values, which is one more than the largest.

    The special case for 0... so if you don't know WinAPI, you might not know which integer type DWORD resolves to, but it is clearly some integer type, which means true converts to 1, not 0. That's not WinAPI, that's standard C++. 2 to the power 0 is 1, so this is the right answer, but I don't know how "wisely" this check is performed, since going through the loop 0 times would produce the same result. I'm reminded of the times I've seen if (!container.empty()) { } around a loop that iterates over the container - if the loop would run zero times just let it run zero times. Don't add extra code just to do nothing instead of nothing!

    DWORD CBitOps::BitPower(WORD n)
{
    if (n >= 8 * sizeof(DWORD)) return 0; /* behaviour preserved - optionally throw or somesuch instead. */
    
    return (DWORD)1 << n;
}
  • MiserableOldGit (unregistered)

    I get the point about not mixing up FP and integer approaches, but surely if feeding something guaranteed to be an integer into an exponential function with another hard coded integer could give you anything other than an integer, you've got some pretty major problems to deal with that won't be solved frigging about with that function!

  • Foo AKA Fooo (unregistered) in reply to MiserableOldGit

    pow (10, 1000) -> inf // not an integer pow (0, -1) -> inf // not an integer pow (10, -10) -> 1e-10 // not an integer pow (10, -1000) -> 0 // integer, but not the mathematically correct result pow (9, 20) -> 12157665459056928768 // integer, but not correct (powers of 9 are always odd)

    I know that's not relevant to the problem at hand, just a warning to be careful with generalized statements about FP.

    More to the point, "uint32_t a = 50, b = pow (2, a);" yields 4294967295 -- at least with my compiler. I'd have to check if that's actually guaranteed or even UB, anyway most likely not better than the 0 that the bit shift operator gives for unsigned types.

    And that's not even talking about performance.

  • Foo AKA Fooo (unregistered) in reply to Foo AKA Fooo

    Argh, messed up formatting again, hope you can read it anyway.

  • Sole Purpose Of Visit (unregistered) in reply to Foo AKA Fooo

    I've never tried this, and I suppose I should look it up in the spec -- C99 at least, although it would be quite interesting in K&R -- but I wonder what happens when C does its usual implicit conversion of a float to an unsigned int (where the float is inf)? Either UB or max uint, I would guess. Not that either would be pleasant.

    I'd imagine (and again I haven't checked the specs) that converting 1En, where n < 0, would simply result in zero. Which, arguably, is the correct result in this case.

    But I'd still argue for language-specific implementation. Use a shift and some sort of sizeof check, for goodness' sake.

    I'm thinking that this would be an excellent interview question, even as posed in the OP. If you want to hire a programmer with some vague ability in C/C++, it would be interesting to see what the candidate comes up with. It shouldn't even take them more than a minute to answer coherently, and coherently would be a good enough discriminator.

  • Sole Purpose Of Visit (unregistered) in reply to Sole Purpose Of Visit

    Then again, as per the discussion a few days ago, 1En where n < 0 might very well invoke the part of the specs where "overflow is not allowed", and consequently you'd end up with something like the result X being turned into max unsigned int modulo X ... which would be ... entertaining. If that were to happen, there's a tiny but not zero possibility that the eventual result would be 0 < result < 64, which would be, ahem, embarrassing.

  • (nodebb)

    Bonus points for hungarian notation.

  • Sole Purpose Of Visit (unregistered) in reply to molleafauss

    Double Plus Ungood points for using "System Hungarian Notation" rather than "Application Hungarian Notation."

    Refer to Nathan's original concept for Minus Minus Clarification.

  • (nodebb)

    Maybe it's just me, but the fact that the output is coming out in a DWORD suggests that there are only 32 possible outputs for this function. Couldn't this have been solved much more simply with a lookup table?

    (Although I agree, the bitshift approach is probably the most suitable for the mythical future world in which we have 128-bit and 256-bit computers.)

  • Worf (unregistered) in reply to Steve_The_Cynic

    DWORD is defined in Windows (going by Hungarian notation as well) as 32-bit unsigned int (== DWORD32)

    It works if n is 32 or greater as well.

    (1 << n) will be 0 if n is 32 or greater. Subtract 1 to get 0xFFFFFFFF, which is the correct value for an unsigned 32 bit integer. Granted, the computer could explode since C underflow is supposed to be undefined, but I believe on Windows it's actually properly defined behavior.

    If you use DWORDLONG or DWORD64 (64 bit integer), it works as expected as well.

  • MiserableOldGit (unregistered) in reply to Foo AKA Fooo

    Indeed, but if you are hitting range limits that is a different problem that generally applies. Ditto feeding negatives into the functions. As you say, irrelevant in this example.

  • Foo AKA Fooo (unregistered) in reply to stoborrobots

    Why on earth would you do a table lookup for something that has a built-in operation readily available? (Yes, with range limits, but so does a table.)

    How would you construct the table? Manually, and risk errors like we've seen so often on this site? Automatically generated, then how would would the generator compute the values, not by any chance via bit shift?

    Oh wait, you're getting paid by LOC, and such a table gives you 32 lines and some easily, right? :)

  • Stella (unregistered)

    "true" and "false" are defined to be converted to 1 and 0 respectively, so that check is superfluous. That still doesn't make it better, though.

  • Foo AKA Fooo (unregistered) in reply to Worf

    Nice point, hadn't noticed so far. As Anonymous pointed out, unsigned overflow/underflow is well-defined in C, not only on Windows. And since WORD is also an unsigned type I assume, n (i.e. wNrOfBits) cannot be negative, so "((ResType)1 << n) - 1" should indeed work for any value of n and any bit size. (The cast must be done before the shift, or else the shift would be done as int.)

  • (nodebb) in reply to Foo AKA Fooo

    Shift of a numerical type with a size of n bits by more than n bits is undefined. You are right that the integer underflow/overflow for addition/subtraction is then well defined (at least since C++ had at last "confirmed" 2-complement as the only legal implementation of signed arithmetic), but the undefined behavior was the shift in the first place.

    Addendum 2021-02-26 01:51: It works on x86, but that doesn't make it less of undefined behavior.

    Addendum 2021-02-26 01:56: Double check with https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators

    Since it's UB, the compiler is then allowed to assume the entire expression is UB, and discard anything depending on a definite result.

    Meaning it will bite you in the form of breaking if you ramp up the optimization level, and the shift happens to become resolvable at compile time. At which point it just stops working, because it had been illegal in the first place.

  • 516052 (unregistered)

    I love the smell of undefined behaviour in the morning. It takes me back to when I was young.

  • (nodebb) in reply to Ext3h

    Addendum 2021-02-26 01:51: It works on x86, but that doesn't make it less of undefined behavior.

    I thought that shifts and rotates on x86 (386+) shift by N modulo bitsize, so shifting a 32-bit quantity by 32 bits is a no-op. (It's probably part of why it's UB in C/C++.)

    Either way, it's UB, so you don't know what will happen.

    And:

    Since it's UB, the compiler is then allowed to assume the entire expression is UB, and discard anything depending on a definite result.

    More to the point, it's also allowed to assume that you've checked elsewhere that the call will not invoke UB, and compile it whatever way is convenient.

    Or if it can verify that this function will inevitably invoke UB, it's allowed to delete its entire contents and replace them by return 42;, or even to just delete the function (on the basis that you know it will invoke UB, so you won't call it anywhere) and fail at link time.

    Undefined behaviour is exactly that, undefined, and anything can happen.

  • Best Of 2021 (unregistered)

    return (DWORD)-1; // This function is probably only called with n=32 anyway

    (1 << n) - 1 is the mathematically right answer. But can you avoid an overflow with [(1 << (n-1)) - 1] + [1 << (n - 1)]?

    This needs the special case for n = 0.

    Of course if the function is "get number of values that fit in this field", you can never represent that number in the same field type. E.g. in decimal, the answer to 'how many values can fit in a 2 digit field' is 100, which doesn't fit in a two digit field.

  • J.G.Harston (unregistered) in reply to Smithers

    return (DWORD)1 << n;

    If a DWORD is 32 bits, what's (DWORD)1<<32 going to return?

    If DWORD is 32 bits, it can hold 0 to 4294967295. 1<<32 is 4294967296. How is DWORD going to hold DWORD_MAX+1 ?

    That's why I recommended the mangled ((1<<(n-1))-1)*2+1 mess above. If n=32 it gives: ((1<<(n-1))-1)*2+1 ((1<<(31))-1)*2+1 ((2147483648)-1)*2+1 (2147483647)*2+1 4294967294+1 4294967295

    ...which is 0xFFFFFFFF which fits in 32 bits.

    ...assuming unsigned arithmetic.

  • J.G.Harston (unregistered)

    Argh! Deformatter burn in hell!!!

    If n=32 it gives:

    ((1<<(n-1))-1)*2+1

    ((1<<(31))-1)*2+1

    ((2147483648)-1)*2+1

    (2147483647)*2+1

    4294967294+1

    4294967295

    has that worked?

  • Anonymous') OR 1=1; DROP TABLE wtf; -- (unregistered) in reply to Steve_The_Cynic

    From a C or C++ compiler's perspective, you're exactly right that shifting a value in either direction by more than its size in bits has undefined behavior, so the compiler can do whatever it wants.

    From a machine code perspective, the behavior is well-defined. On x86 and x86-64, instructions like shr and shl discard the upper bits of the shift and only shift by the bottom 5/6 bits: a shift by 32 will by a no-op (for 32-bit registers), a shift by 33 will be a shift by 1, etc. Conversely on ARM, the shift instructions do use all the bits and will give the mathematically correct result modulo the output register size: a shift by 32 or more will give a result of 0 (again in 32-bit mode).

    But of course you should only rely on that behavior if you're hand-writing the assembly code or trying to understand the behavior of an existing piece of compiled assembly. You should never rely on the compiler generating correct assembly if the original C/C++ invoked UB.

  • John (unregistered)

    Good ole FORTRAN IV lives on. Name the variable with a "w" because its a "w"ord.

  • (nodebb) in reply to J.G.Harston

    If a DWORD is 32 bits, what's (DWORD)1<<32 going to return?

    A nasal demon, because shifing by an amount that's equal to or greater than the word size is Undefined Behaviour.

  • Ann Onymous (unregistered)

    My favourite part is that the return value is always wrong. For example, when passing 4 as an argument, the result is 16, and not 15.

  • markm (unregistered)

    The lower bound check is never needed for an unsigned input. If the output is the number of unsigned integers (or states) that can be expressed in wNrOfBits, then 0 bits can express just one value: 0. With no check, the for loop drops through and the function returns 1. But you need an upper bound check, because (assuming DWORD is uint32_t) it cannot return an accurate value for wNrOfBits over 32, and probably will return 0. (This is assuming the compiler either does not add bound checks for the multiply, or sets the result to 0 if overflows.)

    To correct this to return the highest value, you want (2 to the power of wNrOfBits) -1. That will return 0 = 1 - 1 for wNrOfBits = 0. Any nonzero number to the power of 0 is 1, and the highest number you can express with 0 bits is either 0 or undefined. (Undefined would require throwing an exception, and this example clearly avoided using exceptions). But a more efficient way is: ((DWORD) 1 << wNrOfBits) - 1.

    You still need an upper bounds check if the compiler limits the right operand of << by taking the modulo 32. (This only requires a bitwise AND to mask the upper bits: n && 31.)

  • (nodebb)

    We are TRWTF, or at least some of us are. And I include Remy in this.

    The function's name, BitPower implies that it returns the value of the bit that is pow(2,wNrOfBits) rather than the maximum number that can be expressed with wNrOfBits bits. So in all the above analysis, the act of subtracting 1 before returning is wrong.

    The constraint on wNrOfBitsshould be that it is strictly greater than zero and not greater than or equal to 32 (the number of bits in DWORD), because if not DWORD cannot represent the result (if greater than 31), or the result is not well defined (if zero). (Um, if you don't have any bits, you can't represent any numbers. On the other hand, BitPower should return 1 for the zero case. Debate...)

    So:

    WORD CBitOps::BitPower(WORD wNrOfBits)
{
    if (wNrOfBits == 0)
    {
        throw std::range_error("BitPower called with zero");
    }
    else if (wNrOfBits >= 32)      
    {
        throw std::range_error("BitPower called with 32 or more");
    }
    else
        return ((DWORD)1) << wNrOfBits;
}

    Optional: merge the two throws. Optional: align the return for zero with the name of the function. Optional: change the name of the function if you want it to really be the number of values you can represent.

  • Quirkafleeg (unregistered)

    More Power!!! Not just a bit...

    ...I'll get my coat...

Leave a comment on “A Bit of Power”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article