# Lolling at programmers, how many ways are there to create a bitmask ? ;) :)

Discussion in 'C Programming' started by Skybuck Flying, May 24, 2010.

1. ### Skybuck FlyingGuest

Ok people,

I keep coming across different ways in source codes for creating a bit mask
for a certain ammount of bits and it's kinda funnieing me out ! =D

Therefore to have some fun, it's time to create a thread dedicated to
creating bitmasks... how many ways are there ?

So far I have come across these methods:

1. (My own way Mask := not word(65535 shl BitCount); // not 1111000 =
0000111

2. Mask := (1 shl BitCount)-1; // 10000-1 = 09999 = 01111

3. Mask := (\$FFFF shl BitCount) xor \$FFFF; // 1111000 xor 1111111 = 0000111

I also wonder which one would be fastest, since processors might execute
instructions in different alu's en such...
Maybe processors have special "boolean/logic" units and "arithmetic units".

To what category would shl belong ? (Maybe "bit logic unit" ?)

them to this thread for the fun of it ! =D

Bye,
Skybuck =D

Skybuck Flying, May 24, 2010

2. ### Guest

Re: Lolling at programmers, how many ways are there to create a

If you're dealing with meaningful bits then use a set of an enumerated
value.

type
TBitFlags = (bfBit0, bfBit1, bfBit2, bfBit3,
bfBit4, bfBit5, bfBit6, bfBit7);
TBitFlagSet = set of TBitFlags;

const
AllBits : TBitFlagSet = [bfBit0..bfBit7];
TwoBits : TBitFlagSet = [bfBit2, bfBit5];

You can give your TBitFlags definition meaningful names and get

Alan Lloyd

, May 24, 2010

3. ### Skybuck FlyingGuest

Sets in pascal are easy to use but they are very slow.

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
4. ### James HarrisGuest

Re: Lolling at programmers, how many ways are there to create a

On 24 May, 17:23, "Skybuck Flying" <> wrote:
> Ok people,
>
> I keep coming across different ways in source codes for creating a bit mask
> for a certain ammount of bits and it's kinda funnieing me out ! =D
>
> Therefore to have some fun, it's time to create a thread dedicated to
> creating bitmasks... how many ways are there ?
>
> So far I have come across these methods:
>
> 1. (My own way   Mask := not word(65535 shl BitCount);  // not 1111000 =
> 0000111
>
> 2. Mask := (1 shl BitCount)-1;  // 10000-1 = 09999 = 01111
>
> 3. Mask := (\$FFFF shl BitCount) xor \$FFFF; // 1111000 xor 1111111 = 0000111
>
> I also wonder which one would be fastest, since processors might execute
> instructions in different alu's en such...
> Maybe processors have special "boolean/logic" units and "arithmetic units".

"Bitmasks" are just bit patterns used in bitwise logic such as 0b1100.
You mean masks for the lowest N bits of a value, i.e. a specific type

Your option 2 is very good! As well as being fast it works regardless
of word size, something the other two fail to do.

As for speed, any of these should be much faster than many
alternatives since they use only simple operations which any self-
respecting CPU will have in its armoury. Your option 2 should compile
on x86-32 to something like

mov eax, 1
shl eax, cl
dec eax

Note there's no range checking on the number of bits to shift (in the
cl register). IIRC if too many are specified the processor will mask
the value keeping just the lower five bits rather than maxing it out.
For example, if you specified a shift of 63 (0b0011_1111) it would
shift 31 (0b0001_1111) places. If that's not what's wanted a test for
range would be needed. This also applies to options 1 and 3 and all
solutions where a shift is required if that shift amount is not a
constant.

BTW, your options 1 and 3 are basically the same as each other. An xor
with a mask of all 1s has the same effect as a not operation. Assuming
32-bit arithmetic, not your 16-bit, they should become something like

mov eax, -1
shl eax, cl
not eax

A word about the limits of these code fragments. It looks like both
pieces of code will work with a shift amount in the range 0 to 31.
Anything 32 or above (which is not to be masked) would need a little
bit of extra code.

The object code for your option 2 should be a little bit shorter than
code for the other two.

James

James Harris, May 25, 2010
5. ### Skybuck FlyingGuest

Cool and handy too ! =D, I shall add this method of yours as number 4.

1. (Skybuck) Mask := not word(65535 shl BitCount); // not 1111000 =
0000111

2. (Michael Vinther) Mask := (1 shl BitCount)-1; // 10000-1 = 09999 = 01111

3. (Skamradt) (Mask := (\$FFFF shl BitCount) xor \$FFFF; // 1111000 xor
1111111 = 0000111

4. (MitchAlsup) Mask := not word((not 0) shl BitCount); // not((not 0 =
1111111) shl 3 = 1111000) = 0000111

So far it seems method 2 is the best/shortest at least in Delphi 2007
compiler.
Method 2 works well for functions and inlining as well, some of the others
seem to become bigger when inlined ?!?
(Actual speed is yet to be determined )

It could be interesting to see how a C compiler compiles it...

For now here is the Delphi 2007 test program, and the assemblies of inlined
vs non-inlined:

// *** Begin of Test Program ***

program TestProgram;

{\$APPTYPE CONSOLE}

{

TestProgram to test and analyze calculation for BitMasks.

version 0.01 created on 25 may 2010 by Skybuck Flying.

When the functions are not inlined all versions use 5 instructions.
(including the return).

However when inline directive happens something interesting happens.

Some versions will be 4 instructions and some 5 some maybe even more.

I guess it depends on how the Delphi 2007 compiler inlines it... ?!?

Re-ordering the code didn't really help...

Mask2MichaelVinther seems to be the best one so far,

Shortest in both modes, uses the least ammount of "instruction bytes".

Actual speed is yet to be determined !

}

uses
SysUtils;

function Mask1Skybuck( ParaBitCount : byte ) : word; inline;
begin
result := not word(65535 shl ParaBitCount);
end;

function Mask2MichaelVinther( ParaBitCount : byte ) : word; inline;
begin
result := (1 shl ParaBitCount)-1;
end;

begin
result := word(\$FFFF shl ParaBitCount) xor \$FFFF;
end;

function Mask4MitchAlsup( ParaBitCount : byte ) : word; inline;
begin
result := not word((not 0) shl ParaBitCount);
end;

procedure Main;
var
vBitCount : word;
begin
vBitCount := 16;

end;

begin
try
{ TODO -oUser -cConsole Main : Insert code here }
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
end.

{
Inlined version:

TestProgram.dpr.51: begin
00408E44 53 push ebx
00408E45 56 push esi
00408E46 57 push edi
TestProgram.dpr.52: vBitCount := 16;
00408E47 66BE1000 mov si,\$0010
00408E4B 8BDE mov ebx,esi
00408E4D 8BCB mov ecx,ebx
00408E4F 66BFFFFF mov di,\$ffff
00408E53 66D3E7 shl di,cl
00408E56 66F7D7 not di
00408E59 0FB7D7 movzx edx,di
00408E5C A1F0A94000 mov eax,[\$0040a9f0]
00408E61 E8CEA8FFFF call @Write0Long
00408E66 E801A9FFFF call @WriteLn
00408E6B E86C9FFFFF call @_IOTest
00408E70 8BCB mov ecx,ebx
00408E72 66BF0100 mov di,\$0001
00408E76 66D3E7 shl di,cl
00408E79 4F dec edi
00408E7A 0FB7D7 movzx edx,di
00408E7D A1F0A94000 mov eax,[\$0040a9f0]
00408E87 E8E0A8FFFF call @WriteLn
00408E8C E84B9FFFFF call @_IOTest
00408E91 8BCE mov ecx,esi
00408E93 66BFFFFF mov di,\$ffff
00408E97 66D3E7 shl di,cl
00408E9A 6681F7FFFF xor di,\$ffff
00408E9F 0FB7D7 movzx edx,di
00408EA2 A1F0A94000 mov eax,[\$0040a9f0]
00408EA7 E888A8FFFF call @Write0Long
00408EAC E8BBA8FFFF call @WriteLn
00408EB1 E8269FFFFF call @_IOTest
00408EB6 8BCE mov ecx,esi
00408EB8 66BFFFFF mov di,\$ffff
00408EBC 66D3E7 shl di,cl
00408EBF 66F7D7 not di
00408EC2 0FB7D7 movzx edx,di
00408EC5 A1F0A94000 mov eax,[\$0040a9f0]
00408ECA E865A8FFFF call @Write0Long
00408ECF E898A8FFFF call @WriteLn
00408ED4 E8039FFFFF call @_IOTest
TestProgram.dpr.65: end;
00408ED9 5F pop edi
00408EDA 5E pop esi
00408EDB 5B pop ebx
00408EDC C3 ret

}

{

Non-inlined/function version:

TestProgram.dpr.29: result := not word(65535 shl ParaBitCount);
00408E44 8BC8 mov ecx,eax
00408E46 66B8FFFF mov ax,\$ffff
00408E4A 66D3E0 shl ax,cl
00408E4D 66F7D0 not ax
TestProgram.dpr.30: end;
00408E50 C3 ret
00408E51 8D4000 lea eax,[eax+\$00] // ignored/filling
TestProgram.dpr.34: result := (1 shl ParaBitCount)-1;
00408E54 8BC8 mov ecx,eax
00408E56 66B80100 mov ax,\$0001
00408E5A 66D3E0 shl ax,cl
00408E5D 48 dec eax
TestProgram.dpr.35: end;
00408E5E C3 ret
00408E5F 90 nop // ignored/filling
TestProgram.dpr.39: result := word(\$FFFF shl ParaBitCount) xor \$FFFF;
00408E60 8BC8 mov ecx,eax
00408E62 66B8FFFF mov ax,\$ffff
00408E66 66D3E0 shl ax,cl
00408E69 6635FFFF xor ax,\$ffff
TestProgram.dpr.40: end;
00408E6D C3 ret
00408E6E 8BC0 mov eax,eax // ignored/filling
TestProgram.dpr.44: result := not word((not 0) shl ParaBitCount);
00408E70 8BC8 mov ecx,eax
00408E72 66B8FFFF mov ax,\$ffff
00408E76 66D3E0 shl ax,cl
00408E79 66F7D0 not ax
TestProgram.dpr.45: end;
00408E7C C3 ret
00408E7D 8D4000 lea eax,[eax+\$00]
TestProgram.dpr.51: begin
00408E80 53 push ebx
00408E81 56 push esi
00408E82 57 push edi
TestProgram.dpr.52: vBitCount := 16;
00408E83 66BE1000 mov si,\$0010
00408E87 8BDE mov ebx,esi
00408E89 8BC3 mov eax,ebx
00408E90 8BF8 mov edi,eax
00408E92 0FB7D7 movzx edx,di
00408E95 A1F0A94000 mov eax,[\$0040a9f0]
00408E9A E895A8FFFF call @Write0Long
00408E9F E8C8A8FFFF call @WriteLn
00408EA4 E8339FFFFF call @_IOTest
00408EA9 8BC3 mov eax,ebx
00408EB0 8BF8 mov edi,eax
00408EB2 0FB7D7 movzx edx,di
00408EB5 A1F0A94000 mov eax,[\$0040a9f0]
00408EBA E875A8FFFF call @Write0Long
00408EBF E8A8A8FFFF call @WriteLn
00408EC4 E8139FFFFF call @_IOTest
00408EC9 8BC3 mov eax,ebx
00408ED0 8BF8 mov edi,eax
00408ED2 0FB7D7 movzx edx,di
00408ED5 A1F0A94000 mov eax,[\$0040a9f0]
00408EDA E855A8FFFF call @Write0Long
00408EDF E888A8FFFF call @WriteLn
00408EE4 E8F39EFFFF call @_IOTest
00408EE9 8BC3 mov eax,ebx
00408EF0 8BF8 mov edi,eax
00408EF2 0FB7D7 movzx edx,di
00408EF5 A1F0A94000 mov eax,[\$0040a9f0]
00408EFA E835A8FFFF call @Write0Long
00408EFF E868A8FFFF call @WriteLn
00408F04 E8D39EFFFF call @_IOTest
TestProgram.dpr.65: end;
00408F09 5F pop edi
00408F0A 5E pop esi
00408F0B 5B pop ebx
00408F0C C3 ret

}

// *** End of Test Program ***

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
6. ### Skybuck FlyingGuest

Probably a range/overflow checking bug in Delphi 2007 compiler.

However Michael's Code is a bit dangerous because of the way Delphi compiles
it:

At first glance during testing apperently it doesn't require a "word"
typecast to make it safe:

function Mask2MichaelVinther( ParaBitCount : byte ) : word; inline;
begin
result := (1 shl ParaBitCount)-1;
end;

Carefully looking at this function makes it suspicious

1 shl 16 would become 0.

0 - 1 should trigger a range checking exception... but the exception never
occurs.

Even when range+overflow checking is on and inlining is off the code doesn't
trip:

It seems to be a Delphi 2007 compiler range/overflow checking bug not being
able to detect this scenerio:

"
TestProgram.dpr.40: result := (1 shl ParaBitCount)-1;
00408E4C 8BC8 mov ecx,eax
00408E4E B801000000 mov eax,\$00000001
00408E53 D3E0 shl eax,cl
00408E55 83E801 sub eax,\$01
00408E58 7105 jno \$00408e5f
00408E5F 3DFFFF0000 cmp eax,\$0000ffff // probably bug here... eax will
be \$FFFF FFFF

Unable to determine from intel documentation what cmp and jbe do...
is it A <= B ? or B <= A ?

00408E64 7605 jbe \$00408e6b
TestProgram.dpr.41: end;
00408E6B C3 ret
"

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
7. ### Skybuck FlyingGuest

Probably a range/overflow checking bug in Delphi 2010 compiler as well.

I tested it in Delphi 2010 as well... bug seems to be present there as well.

Same behaviour there... no range/underflow warnings/exceptions for method 2
for BitCount 16.

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
8. ### Skybuck FlyingGuest

The other methods have problems too ofcourse, that's why I added the "word"
typecasts... though when leaving out the "word" typecast not all problems
are detected by Delphi's range checking capabilities.

Therefore it's worth bitching about Delphi not being able to detect
problems:

> 1. (Skybuck) Mask := not word(65535 shl BitCount); // not 1111000 =
> 0000111

This method without the typecast should have raised an exception since 65535
is being shifted out and becomes to large for a word...

Therefore in 16 bit it will work but in 32 bit it will still bug out, a
typecast for longword will fix it again.

All methods have this problem, therefore all methods require a typecast to
be on the safe side if range/overflow checking is to be enabled.

>
> 2. (Michael Vinther) Mask := (1 shl BitCount)-1; // 10000-1 = 09999 =
> 01111
>
> 3. (Skamradt) (Mask := (\$FFFF shl BitCount) xor \$FFFF; // 1111000 xor
> 1111111 = 0000111
>
> 4. (MitchAlsup) Mask := not word((not 0) shl BitCount); // not((not 0 =
> 1111111) shl 3 = 1111000) = 0000111

Moral of the story:

Code designed will work in 16 bit in Delphi but would present problems in 32
bit.

problems/versions.

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
9. ### Skybuck FlyingGuest

Hmm kinda interesting... method 3 does bitch about the shl being to large...
in 16 bit version.

The other ones don't do that...

Apperently it all depends on what kind of assembler is generated by the
compiler

The method is almost similiar except for the xor...

Maybe the xor triggers a different way of assembling the code...

Or maybe it's just the code order... but I would place my bet on the xor
triggering something inside the compiler

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
10. ### Skybuck FlyingGuest

Wow when the bit count changes from 16 to 15 then suddenly my method starts
to trip range checking exceptions as well !

Totally funny ! =D

This is some fun code we have here ladies and gentlemen !

Bye,
Skybuck =D

Skybuck Flying, May 25, 2010
11. ### Skybuck FlyingGuest

Wow method 1 even trips for a BitCount of 0 ?!?

How is that possible ?

Seems like Delphi compiler has some real issue's with this code and it's
range checking capabilities ?!

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
12. ### Skybuck FlyingGuest

Method 3 does work for BitCount of 0 and starts to trip at BitCount 1 !

Most amuzing ! =D

Bye,
Skybuck =D

Skybuck Flying, May 25, 2010
13. ### Skybuck FlyingGuest

I guess the moral of this story is:

Delphi's Overflow/Range checking cannot be trusted at all...

I already knew it was bad and missed some cases... but this is getting
pretty ridicules!

It even detects cases/"fake bugs" which seem totally legal and therefore
shouldn't have been detected at all ?! wow ?!

None-the-less it always helps having it on... but it should not be relied on
to detect everything.

Bye,
Skybuck =D

Skybuck Flying, May 25, 2010
14. ### Skybuck FlyingGuest

Create test programs which test full ranges, and have independent code which
test for correct input, correct memory and correct output value's... bit by
bit if necessary.

Such test programs will catch all cases.

I already created such a test program to test my WriteBitfield routines...
and the test program proved to be highly successfull and usefull ! =D

Bye,
Skybuck.

Skybuck Flying, May 25, 2010

Re: Lolling at programmers, how many ways are there to create a

On May 25, 6:54 am, "Skybuck Flying" <>
wrote:
>
> Create test programs which test full ranges, and have independent code which
> test for correct input, correct memory and correct output value's... bit by
> bit if necessary.
>
> Such test programs will catch all cases.
>
> I already created such a test program to test my WriteBitfield routines....
> and the test program proved to be highly successfull and usefull ! =D
>

<off topic>
I can't tell if you are holding a conversation with yourself or if the
computers at my job are just doing some kind of wierd filtering that
isn't allowing me to see who you are talking to.
</off topic>

16. ### James HarrisGuest

Re: Lolling at programmers, how many ways are there to create a

On 25 May, 16:51, Andy 'Krazy' Glew <> wrote:
....
> When shifts are slow, instruction sets are advised to have instructions to generate bitmasks.
>
>
> but even these have 2 6 bit constants (on a 64 bit machine).
>
>
> not much better, except for small masks.

Right. For what the OP is looking for (rightmost N bits set) a simple
lookup table would do.

James

James Harris, May 25, 2010
17. ### Skybuck FlyingGuest

"James Harris" <> wrote in message
news:...
> On 25 May, 16:51, Andy 'Krazy' Glew <> wrote:
> ...
>> When shifts are slow, instruction sets are advised to have instructions
>>
>>
>> but even these have 2 6 bit constants (on a 64 bit machine).
>>
>>
>> not much better, except for small masks.

>
> Right. For what the OP is looking for (rightmost N bits set) a simple
> lookup table would do.

Seems like a waste of L1 data cache to me... it will already be massively
used me thinks...

I could be wrong though...

None the less, the lookup table method is idea another way to do it, I have
seen it before...

LookupTable : array[0..32] of longword;

^ BitCount goes into it as the index and a longword goes out with a maximum
of 32 bits

So that'll be number 5. I'll have to consult my "source "databas"" to see
who's name it was who's I first saw !

Bye,
Skybuck.

Skybuck Flying, May 25, 2010
18. ### James HarrisGuest

Re: Lolling at programmers, how many ways are there to create a

On 25 May, 23:32, "Skybuck Flying" <> wrote:
> "James Harris" <> wrote in message
>
> news:...
>
> > On 25 May, 16:51, Andy 'Krazy' Glew <> wrote:
> > ...
> >> When shifts are slow, instruction sets are advised to have instructions

>

>
> >> but even these have 2 6 bit constants (on a 64 bit machine).

>

>
> >> not much better, except for small masks.

>
> > Right. For what the OP is looking for (rightmost N bits set) a simple
> > lookup table would do.

>
> Seems like a waste of L1 data cache to me...

Possibly, though that was in the context of Andy's comment: "When
shifts are slow...." Shifts are fast on the CPUs we normally deal with
which have the silicon to shift all the bit positions at once but
there are/were processors which carry out shifts one bit at a time.
For example, see the timings for the 8086 and the 80286 shift left
here

http://home.comcast.net/~fbui/intel_s.html#sal

Also, if a particular loop doesn't already use much data cache a
lookup table can still be a good way to go. On some CPUs L1 cache
reads can be as fast or nearly as fast as reading registers.

On the other hand bit twiddling can be faster, depending on
requirements and hardware.

YMMV!

James

James Harris, May 26, 2010
19. ### Skybuck FlyingGuest

Yeah, I noticed this problem as well..

It's an outlook express problem.

It doesn't recgonize that I am posting a follow-up to myself.

If it did it would have been clear in the subject line as follows:

Fu: Lolling at programmers, how many ways are there to create a bitmask ?

Follow Up, Not **** U LOL.

Maybe

Fo: is better.

Just like

Bye,
Skybuck =D

Skybuck Flying, May 26, 2010
20. ### MitchAlsupGuest

Re: Lolling at programmers, how many ways are there to create a

On May 25, 10:51 am, Andy 'Krazy' Glew <>
wrote:
> > 4. (MitchAlsup) Mask := not word((not 0) shl BitCount); // not((not 0 =
> > 1111111) shl 3 = 1111000) = 0000111

>
> Trades off constant size for instruction count.

Not in C

Mitch

MitchAlsup, May 26, 2010