I have 8 bool variables, and I want to "merge" them into a byte.
Is there an easy/preferred method to do this?
How about the other way around, decoding a byte into 8 separate boolean values?
I come in assuming it's not an unreasonable question, but since I couldn't find relevant documentation via Google, it's probably another one of those "nonono all your intuition is wrong" cases.
The hard way:
unsigned char ToByte(bool b[8])
{
unsigned char c = 0;
for (int i=0; i < 8; ++i)
if (b[i])
c |= 1 << i;
return c;
}
And:
void FromByte(unsigned char c, bool b[8])
{
for (int i=0; i < 8; ++i)
b[i] = (c & (1<<i)) != 0;
}
Or the cool way:
struct Bits
{
unsigned b0:1, b1:1, b2:1, b3:1, b4:1, b5:1, b6:1, b7:1;
};
union CBits
{
Bits bits;
unsigned char byte;
};
Then you can assign to one member of the union and read from another. But note that the order of the bits in Bits is implementation defined.
Note that reading one union member after writing another is well-defined in ISO C99, and as an extension in several major C++ implementations (including MSVC and GNU-compatible C++ compilers), but is Undefined Behaviour in ISO C++. memcpy or C++20 std::bit_cast are the safe ways to type-pun in portable C++.
(Also, the bit-order of bitfields within a char is implementation defined, as is possible padding between bitfield members.)
Bits though? –
Camm <<. But you can mix both solitions. –
Despoliation unsigned char (not unsigned) to better match the CBits union. –
Variate unsigned char which means there's no trap representation. –
Tails inline uint8_t pack8bools(bool* a)
{
uint64_t t;
memcpy(&t, a, sizeof t); // strict-aliasing & alignment safe load
return 0x8040201008040201ULL*t >> 56;
// bit order: a[0]<<7 | a[1]<<6 | ... | a[7]<<0 on little-endian
// for a[0] => LSB, use 0x0102040810204080ULL on little-endian
}
void unpack8bools(uint8_t b, bool* a)
{
// on little-endian, a[0] = (b>>7) & 1 like printing order
auto MAGIC = 0x8040201008040201ULL; // for opposite order, byte-reverse this
auto MASK = 0x8080808080808080ULL;
uint64_t t = ((MAGIC*b) & MASK) >> 7;
memcpy(a, &t, sizeof t); // store 8 bytes without UB
}
Assuming sizeof(bool) == 1
To portably do LSB <-> a[0] (like the pext/pdep version below) instead of using the opposite of host endianness, use htole64(0x0102040810204080ULL) as the magic multiplier in both versions. (htole64 is from BSD / GNU <endian.h>). That arranges the multiplier bytes to match little-endian order for the bool array. htobe64 with the same constant gives the other order, MSB-first like you'd use for printing a number in base 2.
You may want to make sure that the bool array is 8-byte aligned (alignas(8)) for performance, and that the compiler knows this. memcpy is always safe for any alignment, but on ISAs that require alignment, a compiler can only inline memcpy as a single load or store instruction if it knows the pointer is sufficiently aligned. *(uint64_t*)a would promise alignment, but also violate the strict-aliasing rule. Even on ISAs that allow unaligned loads, they can be faster when naturally aligned. But the compiler can still inline memcpy without seeing that guarantee at compile time.
Suppose we have 8 bools b[0] to b[7] whose least significant bits are named a-h respectively that we want to pack into a single byte. Treating those 8 consecutive bools as one 64-bit word and load them we'll get the bits in reversed order in a little-endian machine. Now we'll do a multiplication (here dots are zero bits)
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
.......h.......g.......f.......e.......d.......c.......b.......a
× 1000000001000000001000000001000000001000000001000000001000000001
────────────────────────────────────────────────────────────────
↑......h.↑.....g..↑....f...↑...e....↑..d.....↑.c......↑b.......a
↑.....g..↑....f...↑...e....↑..d.....↑.c......↑b.......a
↑....f...↑...e....↑..d.....↑.c......↑b.......a
+ ↑...e....↑..d.....↑.c......↑b.......a
↑..d.....↑.c......↑b.......a
↑.c......↑b.......a
↑b.......a
a
────────────────────────────────────────────────────────────────
= abcdefghxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The arrows are added so it's easier to see the position of the set bits in the magic number. At this point 8 least significant bits has been put in the top byte, we'll just need to mask the remaining bits out
So the magic number for packing would be 0b1000000001000000001000000001000000001000000001000000001000000001 or 0x8040201008040201. If you're on a big endian machine you'll need to use the magic number 0x0102040810204080 which is calculated in a similar manner
For unpacking we can do a similar multiplication
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh
× 1000000001000000001000000001000000001000000001000000001000000001
────────────────────────────────────────────────────────────────
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
────────────────────────────────────────────────────────────────
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000
After multiplying we have the needed bits at the most significant positions, so we need to mask out irrelevant bits and shift the remaining ones to the least significant positions. The output will be the bytes contain a to h in little endian.
On newer x86 CPUs with BMI2 there are PEXT and PDEP instructions for this purpose. The pack8bools function above can be replaced with
_pext_u64(*((uint64_t*)a), 0x0101010101010101ULL);
And the unpack8bools function can be implemented as
_pdep_u64(b, 0x0101010101010101ULL);
(This maps LSB -> LSB, like a 0x0102040810204080ULL multiplier constant, opposite of 0x8040201008040201ULL. x86 is little-endian: a[0] = (b>>0) & 1; after memcpy.)
Unfortunately those instructions are very slow on AMD before Zen 3 so you may need to compare with the multiplication method above to see which is better
x86 SIMD has an operation that takes the high bit of every byte (or float or double) in a vector register, and gives it to you as an integer. The instruction for bytes is pmovmskb. This can of course do 16 bytes at a time with the same number of instructions, so it gets better than the multiply trick if you have lots of this to do.
#include <immintrin.h>
inline uint8_t pack8bools_SSE2(const bool* a)
{
__m128i v = _mm_loadl_epi64( (const __m128i*)a ); // 8-byte load, despite the pointer type.
// __m128 v = _mm_cvtsi64_si128( uint64 ); // alternative if you already have an 8-byte integer
v = _mm_slli_epi32(v, 7); // low bit of each byte becomes the highest
return _mm_movemask_epi8(v);
}
There isn't a single instruction to unpack until AVX-512, which has mask-to-vector instructions. It is doable with SIMD, but likely not as efficiently as the multiply trick. See Convert 16 bits mask to 16 bytes mask and more generally is there an inverse instruction to the movemask instruction in intel avx2? for unpacking bitmaps to other element sizes.
How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD has some answers specifically for 8-bits -> 8-bytes, but if you can't do 16 bits at a time for that direction, the multiply trick is probably better, and pext certainly is (except on CPUs where it's disastrously slow, like AMD before Zen 3).
std::bitset. They probably even get the optimization for free if they use the unsigned long long constructor. –
Spurtle unsigned long long constructor (and to_ullong to unpack). Going between the array of bools and the unsigned long longs would still not be free in that you'd still have to do the casts by hand. –
Spurtle to_ullong and the unsigned long long constructor can't use PEXT and PDEP because they just copy the unsigned long long value directly to/from the internal array. The bits in bitset are stored as bits in the array and not one bit per byte. So to_ullong gives you 64 bits and not 8 –
Chavarria gcc 8 and 9 when -O2 is enabled? I get wrong answers after a packing and unpacking when -O2 is used, while it gives correct answers without optimization. Note, using clang, it gives correct answers even when -O2 is on. –
Revolver gcc when -O2 is turned on: I found that using std::memcpy() instead of type punning would resolve the incorrect answer issue. –
Revolver -fno-strict-aliasing or a union. Or just change from bool to char because char* can alias other types –
Chavarria char instead of bool would give me correct answers. But gcc still complains dereferencing type-punned pointer will break strict-aliasing rules. This is interesting behavior of gcc though. –
Revolver uint64_t* to read a char[] object violates strict-aliasing. ISO C only allows it the other way around: using char * to read an object that was originally a uint64_t. If the only access to the char object is through a char*, you're fine, but if there's any use of an automatic or static storage char[], you have UB. This answer should really use memcpy or C++20 std::bitcast, or GNU C typedef uint64_t unaligned_aliasing_u64 __attribute__((aligned(1), may_alias)); to do the type-punning; pointer-casting is never safe. –
Butterbur new or malloc, all the char accesses to it are going to be via char* anyway, and thus aliasing-safe. But if you have a real char array[8] variable declaration somewhere, access to it might not be through a char*. –
Butterbur struct foo{ int a; char b[8];}; then you can do struct assignment of the whole struct even via pointers to it, like foo *p=..., *q=...; and *p = *q. Access to char b[8] is not through a char* in that case, so a compiler could certainly assume that some uint64_t* load or store was unrelated to it. (You might actually need this struct thing for UB to actually happen, or at least to be a problem in practice, not just a char arr[8] local var: [] access works by decay to char*) –
Butterbur memcpy is the safest way to go! –
Revolver pdep vs. How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD. (For my answer on Convert 16 bits mask to 16 bytes mask) –
Butterbur pdep version. I found the easiest way to think through which order is which is: 0x...40201 * 0x80 has 0x80 in the low byte, which the mask+shift will turn into 0x...01. So high bit of the input maps to low byte of the output, and memcpy into bool[] uses native endianness.) –
Butterbur bool a[] = {[7] = 1;} highest bit set as a test input -> 1 or 0x80. I made an edit based on sorting all that out, hopefully making this more usable for future readers. Note that clang on Godbolt uses host headers, so big-endian targets like powerpc64 still use x86 bits/endianness.h and have backwards htole64 / be64. (github.com/compiler-explorer/compiler-explorer/issues/…). But GCC works, and does sometimes constant-propagate through a bool array init -> memcpy -> multiply. –
Butterbur (a & 0x7f) * magic | (a << 56). –
Juglandaceous ((MAGIC*b) & MASK) >> 7 ends up producing 0x1 instead of 0x101010101010101 –
Vinasse You might want to look into std::bitset. It allows you to compactly store booleans as bits, with all of the operators you would expect.
No point fooling around with bit-flipping and whatnot when you can abstract away.
#include <stdint.h> // to get the uint8_t type
uint8_t GetByteFromBools(const bool eightBools[8])
{
uint8_t ret = 0;
for (int i=0; i<8; i++) if (eightBools[i] == true) ret |= (1<<i);
return ret;
}
void DecodeByteIntoEightBools(uint8_t theByte, bool eightBools[8])
{
for (int i=0; i<8; i++) eightBools[i] = ((theByte & (1<<i)) != 0);
}
eightBools[i] is a bool and checking it with == true you can also just write (eightBools[i] == true) == true or ((eightBools[i] == true) == true) == true, but where to stop? And yes, that's worth not up-voting the answer. –
Glissando bool a,b,c,d,e,f,g,h;
//do stuff
char y= a<<7 | b<<6 | c<<5 | d<<4 | e <<3 | f<<2 | g<<1 | h;//merge
although you are probably better off using a bitset
I'd like to note that type punning through unions is UB in C++ (as rodrigo does in his answer. The safest way to do that is memcpy()
struct Bits
{
unsigned b0:1, b1:1, b2:1, b3:1, b4:1, b5:1, b6:1, b7:1;
};
unsigned char toByte(Bits b){
unsigned char ret;
memcpy(&ret, &b, 1);
return ret;
}
As others have said, the compiler is smart enough to optimize out memcpy().
BTW, this is the way that Boost does type punning.
There is no way to pack 8 bool variables into one byte. There is a way packing 8 logical true/false states in a single byte using Bitmasking.
bools into one byte. Of course they're no longer separate C++ bool objects, but all 8 values are all there within the bits of one char or uint8_t. This answer seems unhelpful and pedantic when the desired behaviour was clear. –
Butterbur You would use the bitwise shift operation and casting to archive it. a function could work like this:
unsigned char toByte(bool *bools)
{
unsigned char byte = \0;
for(int i = 0; i < 8; ++i) byte |= ((unsigned char) bools[i]) << i;
return byte;
}
Thanks Christian Rau for the correction s!
short (which may be 1 byte, but will most probably be 2) and not just a char (which is guaranteed to be 1 byte) is...? And also you should use unsigned types and initialize byte properly. Fix those and the answer is much more likely to be correct. But I'm not the down-voter, not yet. –
Glissando unsigned? And what is that \ for? –
Glissando unsigned char byte = \0; is invalid. Either use 0 or '\0' –
Chavarria @Fabian @111111 -
If you want 8 split out bools with less hard-coding, maybe...
bool a,b,c,d,e,f,g,h; # assuming you want [a] at MSB and
# [h] at LSB
char y = a << 7 | b<< 6 | c << 5 | d << 4 | e << 3 | f << 2 | g << 1 | h
char y = h|(g|(f|(e|(d|(c|(b|a << 1)<< 1)<< 1)<< 1)<< 1)<< 1)<< 1
... instead of 7 different shifting amounts, a nested form allow re-using the same shifting constant over and over again,
with the added benefit of placing all the bools/digits together on one side, and all the shifting amounts on the other side
The arithmetic equivalent expressions would be (they're all identical) -
char y = h + (g + (f + (e + (d + (c + (b + a * 2) * 2) * 2) * 2) * 2) * 2) * 2
char y = 2 * (2 * (2 * (2 * (2 * (2 * (2 * a + b) + c) + d) + e) + f) + g) + h
char y = 2 * ( 2 * ( 2 * ( 2 * ( 2 * ( 2 * ( 2 * (\
a ) + b ) + c ) + d ) + e ) + f ) + g ) + h
Personally I like the last form the most because it's a full-blown base-conversion routine without requiring the audience to even have any understanding what base and exponents are, or what shifting entails as long as they understand addition and multiplication.
© 2022 - 2024 — McMap. All rights reserved.