0

Following my previous question, I need to create a value consisting of a solid range of bits set to 1. I used the following function:

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
    mask |= ((1 << count) - 1) << first;
}

However, as discovered, it didn't work correctly for count = 32. The outcome of 1 << count in such a case theoretically is undefined behavior (or result), and practically on x86 it's 1, because shift operand is treated modulo 32.

I want to fix this expression to work correctly for this extreme case also. What's the most simple/nice/efficient way to do this?

Handling this specific case via branching (if, ?) is kinda simple, though ugly, and I bet it's inefficient either.

Another way is to promote the shift operand to a greater type (64bit). I mean the following:

void MaskAddRange(UINT& mask, UINT first, UINT count)
{
    mask |= (UINT(unsigned __int64(1) << count) - 1) << first;
}

Is there a better way?

Community
  • 1
  • 1
valdo
  • 12,632
  • 2
  • 37
  • 67
  • Hmm. Can you add a simple, short, concise description of the required behaviour of your function? I'd prefer not to have to reverse-engineer the requirements from the code that's in question. – Kerrek SB Mar 25 '12 at 14:27
  • `void MaskAddRange(UINT& mask, UINT first, UINT count){...}` is a syntax error in C. Maybe you mean C++? – wildplasser Mar 25 '12 at 14:28
  • @wildplasser: yes, I meant C++. I didn't want to tag the question C++, because the question itself is not related to C++ – valdo Mar 25 '12 at 14:54
  • In C one would probably write something like `mask |= ((1ull << count) - 1) << first;` and put it in a "function-style" macro, because C knows no call-by-reference. – wildplasser Mar 25 '12 at 15:04

2 Answers2

1

Never assume anything is inefficient unless you can prove it. The if-else may just as well be more efficient on your architecture+OS than the promotion to 64-bit. I don't think there is any other, sane approach than those two you already posted.

I'd go for the if-else because it documents the intent of handling the extreme case. Promoting to 64-bit doesn't indicate that intent.

Irfy
  • 9,323
  • 1
  • 45
  • 67
  • Thank you very much for theoretical essay about the guidelines for writing efficient software. However in my particular case I can easily prove the branching is less efficient than a single CPU instruction (already did this). I also believe that a *sane* approach should be assuming some facts based on the "educated guess", followed by the mandatory verification. – valdo Mar 25 '12 at 14:43
  • P.S. I agree that using explicit `if-else` actually self-documents the intent to handle a particular extreme case, which is somewhat valuable. OTOH speaking more generally I prefer to write something that inherently covers all the extreme cases (if I can). Then it's easier to see the program flow, without the need to mentally consider all the cases. This usually also leads to a better and more universal formulation. – valdo Mar 25 '12 at 14:53
  • Can you provide us with the "single CPU instruction" that you refer to? Because your (or Howard's) function will never ever be a single instruction, I can assure of that. But to cut the discussion short let me say this: on a CPU which supports 64-bit integer operations efficiently, your 64-bit promotion code will be the most efficient. And seeing how you use Windows, you're probably running on a CPU that does support 64-bit integer operations efficiently. – Irfy Mar 25 '12 at 15:14
0

You may use

mask |= (UINT(-1)<<first) & (UINT(-1)>>(32-first-count))

which is more complicated but should work in any case. Efficiency of this expression with respect to other solutions may depend on architecture and compiler.

Howard
  • 38,639
  • 9
  • 64
  • 83
  • Interesting. However it's prone to another extreme case, where `first=0` and `count=0`. – valdo Mar 25 '12 at 14:46