 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best ofâ€¦
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
(1 << n )  1
Admin
For shame, Remy.
DWORD
is just an alias foruint32
, and the consequence of a cast frombool
to an integer type is welldefined 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 methodsstatic
) or it requires an instance to do something noninstancey. 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.Admin
For n strictly less than the number of bits in a
DWORD
, of course, since otherwise the nasal demons of UB bite you.Admin
Well, yes, but it's the native way of doing the job in C. No pointless callouts 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.
Admin
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.
Admin
The presented code is a lot of WTFs, but the suggestion to use floating point arithmetics (pow) also is.
Admin
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 20210225 08:10: PS. This has nothing to do with the WTF in the story, of course.
Admin
@Steve  I have an entire collections of nasaldemons that I have collected over the years... Feel free to come visit... Admission is free, but the exit price is your soul.
Admin
The Wrong BitTwiddler is the one villain even Batman could not deal with.
Admin
Because you can't put a zero in zero bits of storage, you silly goose =)
Admin
The correct function to call (on all machines with powerof2 floating point[1]) is scalb like this:
[1] I haven't gone through the mental gymnastics if this would also work on the IBM S/360 and later which used powerof16 exponents in their FPU
Admin
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.
Admin
Re: ++i vs. i++ That is true, unless you are also extracting the value of the increment/decrement.
vs.
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.
Admin
~( (~0) << n )
Admin
I don't know C++, so maybe DWORD is always nonnegative. ..
Admin
When you see ++i in C code, you know that it was written by a C++ programmer.
Admin
@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 welldefined: 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.)
Admin
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<<(n1)1)*2+1 or something, with range checks.
Admin
Equally equally inescapable are the number of ways to write simple articles wrong...
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!Admin
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!
Admin
pow (10, 1000) > inf // not an integer pow (0, 1) > inf // not an integer pow (10, 10) > 1e10 // 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.
Admin
Argh, messed up formatting again, hope you can read it anyway.
Admin
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 languagespecific 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.
Admin
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.
Admin
Bonus points for hungarian notation.
Admin
Double Plus Ungood points for using "System Hungarian Notation" rather than "Application Hungarian Notation."
Refer to Nathan's original concept for Minus Minus Clarification.
Admin
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 128bit and 256bit computers.)
Admin
DWORD is defined in Windows (going by Hungarian notation as well) as 32bit 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.
Admin
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.
Admin
Why on earth would you do a table lookup for something that has a builtin 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? :)
Admin
"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.
Admin
Nice point, hadn't noticed so far. As Anonymous pointed out, unsigned overflow/underflow is welldefined 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.)
Admin
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" 2complement as the only legal implementation of signed arithmetic), but the undefined behavior was the shift in the first place.
Addendum 20210226 01:51: It works on x86, but that doesn't make it less of undefined behavior.
Addendum 20210226 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.
Admin
I love the smell of undefined behaviour in the morning. It takes me back to when I was young.
Admin
I thought that shifts and rotates on x86 (386+) shift by N modulo bitsize, so shifting a 32bit quantity by 32 bits is a noop. (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:
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.
Admin
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 << (n1))  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.
Admin
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<<(n1))1)*2+1 mess above. If n=32 it gives: ((1<<(n1))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.
Admin
Argh! Deformatter burn in hell!!!
If n=32 it gives:
((1<<(n1))1)*2+1
((1<<(31))1)*2+1
((2147483648)1)*2+1
(2147483647)*2+1
4294967294+1
4294967295
has that worked?
Admin
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 welldefined. On x86 and x8664, 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 noop (for 32bit 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 32bit mode).
But of course you should only rely on that behavior if you're handwriting 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.
Admin
Good ole FORTRAN IV lives on. Name the variable with a "w" because its a "w"ord.
Admin
A nasal demon, because shifing by an amount that's equal to or greater than the word size is Undefined Behaviour.
Admin
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.
Admin
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.)
Admin
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 ispow(2,wNrOfBits)
rather than the maximum number that can be expressed withwNrOfBits
bits. So in all the above analysis, the act of subtracting 1 before returning is wrong.The constraint on
wNrOfBits
should be that it is strictly greater than zero and not greater than or equal to 32 (the number of bits inDWORD
), because if notDWORD
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:
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.
Admin
More Power!!! Not just a bit...
...I'll get my coat...