I was facing this unique problem of generating a bit-mask based on the input parameter. For example,
if param = 2, then the mask will be 0x3 (11b) if param = 5, then the mask will be 0x1F (1 1111b)
This I implemented using a for-loop in C, something like
int nMask = 0; for (int i = 0; i < param; i ++) { nMask |= (1 << i); }
I would like to know if there is a better algorithm ~~~
Calculate the subnet bits by looking at the final 8-bit binary word of the 32-bit binary subnet mask. If the final 8-bit binary word is 10000000, then there is one subnet bit and therefore 25 mask bits. If it is 11000000, then there are two subnet bits and therefore 26 mask bits.
To represent a set of N items we need a sequence of N bits where every bit represents an item in the Set. This sequence of bits used to represent a subset of a set is usually referred to as a mask. For example, the sequence of bits 10101 is a mask used to represent a set of size 5.
In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word, etc. can be set either on or off, or inverted from on to off (or vice versa) in a single bitwise operation.
One thing to notice about bitmasks like that is that they are always one less than a power of two.
The expression 1 << n
is the easiest way to get the n-th power of two.
You don't want Zero to provide a bitmask of 00000001
, you want it to provide zero. So you need to subtract one.
mask = (1 << param) - 1;
Edit:
If you want a special case for param > 32:
int sizeInBits = sizeof(mask) * BITS_PER_BYTE; // BITS_PER_BYTE = 8; mask = (param >= sizeInBits ? -1 : (1 << param) - 1);
This method should work for 16, 32, or 64 bit integers, but you may have to explicitly type the '1'.
C:
#include <limits.h> /* CHAR_BIT */ #define BIT_MASK(__TYPE__, __ONE_COUNT__) \ ((__TYPE__) (-((__ONE_COUNT__) != 0))) \ & (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__)))
C++:
#include <climits> template <typename R> static constexpr R bitmask(unsigned int const onecount) { // return (onecount != 0) // ? (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount)) // : 0; return static_cast<R>(-(onecount != 0)) & (static_cast<R>(-1) >> ((sizeof(R) * CHAR_BIT) - onecount)); }
BIT_MASK(unsigned int, 4) /* = 0x0000000f */ BIT_MASK(uint64_t, 26) /* = 0x0000000003ffffffULL */
#include <stdio.h> int main() { unsigned int param; for (param = 0; param <= 32; ++param) { printf("%u => 0x%08x\n", param, BIT_MASK(unsigned int, param)); } return 0; }
0 => 0x00000000 1 => 0x00000001 2 => 0x00000003 3 => 0x00000007 4 => 0x0000000f 5 => 0x0000001f 6 => 0x0000003f 7 => 0x0000007f 8 => 0x000000ff 9 => 0x000001ff 10 => 0x000003ff 11 => 0x000007ff 12 => 0x00000fff 13 => 0x00001fff 14 => 0x00003fff 15 => 0x00007fff 16 => 0x0000ffff 17 => 0x0001ffff 18 => 0x0003ffff 19 => 0x0007ffff 20 => 0x000fffff 21 => 0x001fffff 22 => 0x003fffff 23 => 0x007fffff 24 => 0x00ffffff 25 => 0x01ffffff 26 => 0x03ffffff 27 => 0x07ffffff 28 => 0x0fffffff 29 => 0x1fffffff 30 => 0x3fffffff 31 => 0x7fffffff 32 => 0xffffffff
First of all, as already discussed in other answers, >>
is used instead of <<
in order to prevent the problem when the shift count is equal to the number of bits of the storage type of the value. (Thanks Julien's answer above for the idea)
For the ease of discussion, let's "instantiate" the macro with unsigned int
as __TYPE__
and see what happens (assuming 32-bit for the moment):
((unsigned int) (-((__ONE_COUNT__) != 0))) \ & (((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))
Let's focus on:
((sizeof(unsigned int) * CHAR_BIT)
first. sizeof(unsigned int)
is known at compile time. It is equal to 4
according to our assumption. CHAR_BIT
represents the number of bits per char
, a.k.a. per byte. It is also known at compile time. It is equal to 8
on most machines on the Earth. Since this expression is known at a compile time, the compiler would probably do the multiplication at compile time and treat it as a constant, which equals to 32
in this case.
Let's move to:
((unsigned int) -1)
It is equal to 0xFFFFFFFF
. Casting -1
to any unsigned type produces a value of "all-1s" in that type. This part is also a compile time constant.
Up to now, the expression:
(((unsigned int) -1) >> ((sizeof(unsigned int) * CHAR_BIT) - (__ONE_COUNT__)))
is in fact the same as:
0xffffffffUL >> (32 - param)
which is the same as Julien's answer above. One problem with his answer is that if param
is equal to 0
, producing the expression 0xffffffffUL >> 32
, the result of the expression would be 0xffffffffUL
, instead of the expected 0
! (That's why I name my parameter as __ONE_COUNT__
to emphasize its intention)
To solve this problem, we could simply add a special case for __ONE_COUNT
equals 0
using if-else
or ?:
, like this:
#define BIT_MASK(__TYPE__, __ONE_COUNT__) \ (((__ONE_COUNT__) != 0) \ ? (((__TYPE__) -1) >> ((sizeof(__TYPE__) * CHAR_BIT) - (__ONE_COUNT__))) : 0)
But branch-free code is cooler, isn't it?! Let's move to the next part:
((unsigned int) (-((__ONE_COUNT__) != 0)))
Let's start from the innermost expression to the outermost. ((__ONE_COUNT__) != 0)
produces 0
when the parameter is 0
, or 1
otherwise. (-((__ONE_COUNT__) != 0))
produces 0
when the parameter is 0
, or -1
otherwise. For ((unsigned int) (-((__ONE_COUNT__) != 0)))
, the type-cast trick ((unsigned int) -1)
is already explained above. Do you notice the trick now? The expression:
((__TYPE__) (-((__ONE_COUNT__) != 0)))
equals to "all-0s" if __ONE_COUNT__
is zero, and "all-1s" otherwise. It acts as a bit-mask for the value we calculated in the first step. So, if __ONE_COUNT__
is non-zero, the mask as no effect and it is the same as Julien's answer. If __ONE_COUNT__
is 0
, it mask away all bits of Julien's answer, producing a constant zero. To visualize, watch this:
__ONE_COUNT__ : 0 Other ------------- -------------- (__ONE_COUNT__) 0 = 0x000...0 (itself) ((__ONE_COUNT__) != 0) 0 = 0x000...0 1 = 0x000...1 ((__TYPE__) (-((__ONE_COUNT__) != 0))) 0 = 0x000...0 -1 = 0xFFF...F
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With