29

I was pondering (and therefore am looking for a way to learn this, and not a better solution) if it is possible to get an array of bits in a structure.

Let me demonstrate by an example. Imagine such a code:

#include <stdio.h>

struct A
{
    unsigned int bit0:1;
    unsigned int bit1:1;
    unsigned int bit2:1;
    unsigned int bit3:1;
};

int main()
{
    struct A a = {1, 0, 1, 1};
    printf("%u\n", a.bit0);
    printf("%u\n", a.bit1);
    printf("%u\n", a.bit2);
    printf("%u\n", a.bit3);
    return 0;
}

In this code, we have 4 individual bits packed in a struct. They can be accessed individually, leaving the job of bit manipulation to the compiler. What I was wondering is if such a thing is possible:

#include <stdio.h>

typedef unsigned int bit:1;

struct B
{
    bit bits[4];
};

int main()
{
    struct B b = {{1, 0, 1, 1}};
    for (i = 0; i < 4; ++i)
        printf("%u\n", b.bits[i]);
    return 0;
}

I tried declaring bits in struct B as unsigned int bits[4]:1 or unsigned int bits:1[4] or similar things to no avail. My best guess was to typedef unsigned int bit:1; and use bit as the type, yet still doesn't work.

My question is, is such a thing possible? If yes, how? If not, why not? The 1 bit unsigned int is a valid type, so why shouldn't you be able to get an array of it?

Again, I don't want a replacement for this, I am just wondering how such a thing is possible.

P.S. I am tagging this as C++, although the code is written in C, because I assume the method would be existent in both languages. If there is a C++ specific way to do it (by using the language constructs, not the libraries) I would also be interested to know.

UPDATE: I am completely aware that I can do the bit operations myself. I have done it a thousand times in the past. I am NOT interested in an answer that says use an array/vector instead and do bit manipulation. I am only thinking if THIS CONSTRUCT is possible or not, NOT an alternative.

Update: Answer for the impatient (thanks to neagoegab):

Instead of

typedef unsigned int bit:1;

I could use

typedef struct
{
    unsigned int value:1;
} bit;

properly using #pragma pack

6
  • 1
    Using bitfields will make your program hard to port... are you sure you need them?
    – Carl Norum
    Commented Nov 15, 2011 at 21:17
  • 8
    @CarlNorum Didn't I mention 10 times that I am just curious?
    – Shahbaz
    Commented Nov 15, 2011 at 21:17
  • 1
    In that case, as far as I know, there's no way to make an array of bitfields.
    – Carl Norum
    Commented Nov 15, 2011 at 21:18
  • 4
    The layout of the bitfields is implementation dependent. So no, rather than being easier it often turns out to be a portability nightmare. The bitwise operators all have well-defined semantics.
    – Carl Norum
    Commented Nov 15, 2011 at 21:20
  • 3
    @CarlNorum: It's only a portability nightmare if you try to cast your struct to/from an array of bytes, and expect a particular layout. If all you want to do is store bits in a struct efficiently, then there's no portability issue. Commented Nov 16, 2011 at 4:50

6 Answers 6

11

NOT POSSIBLE - A construct like that IS NOT possible(here) - NOT POSSIBLE

One could try to do this, but the result will be that one bit is stored in one byte

#include <cstdint>
#include <iostream>
using namespace std;

#pragma pack(push, 1)
struct Bit
{
    //one bit is stored in one BYTE
    uint8_t a_:1;
};
#pragma pack(pop, 1)
typedef Bit bit;

struct B
{
    bit bits[4];
};

int main()
{
    struct B b = {{0, 0, 1, 1}};
    for (int i = 0; i < 4; ++i)
        cout << b.bits[i] <<endl;

    cout<< sizeof(Bit) << endl;
    cout<< sizeof(B) << endl;

    return 0;
}

output:

0 //bit[0] value
0 //bit[1] value
1 //bit[2] value
1 //bit[3] value
1 //sizeof(Bit), **one bit is stored in one byte!!!**
4 //sizeof(B), ** 4 bytes, each bit is stored in one BYTE**

In order to access individual bits from a byte here is an example (Please note that the layout of the bitfields is implementation dependent)

#include <iostream>
#include <cstdint>
using namespace std;

#pragma pack(push, 1)
struct Byte
{
    Byte(uint8_t value):
        _value(value)
    {
    }
    union
    {
    uint8_t _value;
    struct {
        uint8_t _bit0:1;
        uint8_t _bit1:1;
        uint8_t _bit2:1;
        uint8_t _bit3:1;
        uint8_t _bit4:1;
        uint8_t _bit5:1;
        uint8_t _bit6:1;
        uint8_t _bit7:1;
        };
    };
};
#pragma pack(pop, 1)

int main()
{
    Byte myByte(8);
    cout << "Bit 0: " << (int)myByte._bit0 <<endl;
    cout << "Bit 1: " << (int)myByte._bit1 <<endl;
    cout << "Bit 2: " << (int)myByte._bit2 <<endl;
    cout << "Bit 3: " << (int)myByte._bit3 <<endl;
    cout << "Bit 4: " << (int)myByte._bit4 <<endl;
    cout << "Bit 5: " << (int)myByte._bit5 <<endl;
    cout << "Bit 6: " << (int)myByte._bit6 <<endl;
    cout << "Bit 7: " << (int)myByte._bit7 <<endl;

    if(myByte._bit3)
    {
        cout << "Bit 3 is on" << endl;
    }
}
7
  • 2
    About your second method, doesn't that union get all the _bit* bits on the same overlapping bit? Didn't you mean struct Bit{ union{ char _value; struct { char _bit0:1; char _bit1:1; ....} _bits; }; };?
    – Shahbaz
    Commented Nov 15, 2011 at 23:17
  • Could you please explain those pragma packs? Are they standard C, or Visual C specific?
    – Shahbaz
    Commented Nov 15, 2011 at 23:21
  • pragma pack is implementation-defined because it's not pragma STDC (ISO 9899:1999(S)6.10.6.1). As far as I know, it's defined for MSVC and GCC.
    – moshbear
    Commented Nov 16, 2011 at 0:02
  • 2
    Look at en.wikipedia.org/wiki/Data_structure_alignment for a more detailed explanation of exactly what pragma pack does.
    – moshbear
    Commented Nov 16, 2011 at 0:04
  • @Shahbaz, yes it should be how you said, apologize for the late update and thank you.
    – joy
    Commented Dec 24, 2013 at 8:55
6

In C++ you use std::bitset<4>. This will use a minimal number of words for storage and hide all the masking from you. It's really hard to separate the C++ library from the language because so much of the language is implemented in the standard library. In C there's no direct way to create an array of single bits like this, instead you'd create one element of four bits or do the manipulation manually.

EDIT:

The 1 bit unsigned int is a valid type, so why shouldn't you be able to get an array of it?

Actually you can't use a 1 bit unsigned type anywhere other than the context of creating a struct/class member. At that point it's so different from other types it doesn't automatically follow that you could create an array of them.

1
  • 1
    Although I explicitly mentioned I am not interested in libraries (since implementing one myself would be simple anyway), but +1 nonetheless because I learned std::bitset exists.
    – Shahbaz
    Commented Nov 15, 2011 at 21:31
4

C++ would use std::vector<bool> or std::bitset<N>.

In C, to emulate std::vector<bool> semantics, you use a struct like this:

struct Bits {
    Word word[];
    size_t word_count;
};

where Word is an implementation-defined type equal in width to the data bus of the CPU; wordsize, as used later on, is equal to the width of the data bus.

E.g. Word is uint32_fast_t for 32-bit machines, uint64_fast_t for 64-bit machines; wordsize is 32 for 32-bit machines, and 64 for 64-bit machines.

You use functions/macros to set/clear bits.

To extract a bit, use GET_BIT(bits, bit) (((bits)->)word[(bit)/wordsize] & (1 << ((bit) % wordsize))).

To set a bit, use SET_BIT(bits, bit) (((bits)->)word[(bit)/wordsize] |= (1 << ((bit) % wordsize))).

To clear a bit, use CLEAR_BIT(bits, bit) (((bits)->)word[(bit)/wordsize] &= ~(1 << ((bit) % wordsize))).

To flip a bit, use FLIP_BIT(bits, bit) (((bits)->)word[(bit)/wordsize] ^= (1 << ((bit) % wordsize))).

To add resizeability as per std::vector<bool>, make a resize function which calls realloc on Bits.word and changes Bits.word_count accordingly. The exact details of this is left as a problem.

The same applies for proper range-checking of bit indices.

4
  • Thanks for going through the trouble of explaining bit operations, but that was obvious to me. My question was about that specific usage (having the bits manipulated by the compiler rather than me). Again, I am not actually using such a thing, but am merely pondering about it.
    – Shahbaz
    Commented Nov 15, 2011 at 21:29
  • Quoting the JSF Coding Style guide: bitset structs shall be avoided unless interfacing with hardware. There's a good reason for that - they are more trouble than they're worth. I'm pretty sure that's also in MISRA, but I don't have a spare $15 to purchase the paper, so I can't give a definitive answer.
    – moshbear
    Commented Nov 15, 2011 at 21:31
  • 2
    @Shahbaz: No, the compiler cannot do that. Commented Nov 15, 2011 at 22:11
  • Even when interfacing with hardware, native bitfields are of little use, certainly not in a way that is portable and doesn't require the user to meticulously check how their implementation does things before writing any code. I made my own bitfield/endianness libraries - including one that allows 'arrays of bitfields' - to fix this and have never looked back. Commented Jan 20, 2016 at 13:52
2

this is abusive, and relies on an extension... but it worked for me:

struct __attribute__ ((__packed__)) A
{
    unsigned int bit0:1;
    unsigned int bit1:1;
    unsigned int bit2:1;
    unsigned int bit3:1;
};
union U
{
    struct A structVal;
    int intVal;
};

int main()
{
    struct A a = {1, 0, 1, 1};
    union U u;
    u.structVal = a;
    for (int i =0 ; i<4; i++)
    {
        int mask = 1 << i;
        printf("%d\n", (u.intVal &  mask) >> i);
    }
    return 0;
}
0

You can also use an array of integers (ints or longs) to build an arbitrarily large bit mask. The select() system call uses this approach for its fd_set type; each bit corresponds to the numbered file descriptor (0..N). Macros are defined: FD_CLR to clear a bit, FD_SET to set a bit, FD_ISSET to test a bit, and FD_SETSIZE is the total number of bits. The macros automatically figure out which integer in the array to access and which bit in the integer. On Unix, see "sys/select.h"; under Windows, I think it is in "winsock.h". You can use the FD technique to make your own definitions for a bit mask. In C++, I suppose you could create a bit-mask object and overload the [] operator to access individual bits.

-1

You can create a bit list by using a struct pointer. This will use more than a bit of space per bit written though, since it'll use one byte (for an address) per bit:

struct bitfield{
    unsigned int bit : 1;
};
struct bitfield *bitstream;

Then after this:

bitstream=malloc( sizeof(struct bitfield) * numberofbitswewant );

You can access them like so:

bitstream[bitpointer].bit=...
4
  • 1
    Did you actually try this? First of all, sizeof(struct bitfield) on its own is rounded up to int size (I tried this with gcc), so even if this worked, your malloc would be allocating way too much memory. Instead, you would want something like malloc(number_of_bits / CHAR_BIT);. But nevertheless, the padding (again, tried with gcc) makes each element in its own unsigned int, so your bitstream[bitpointer].bit would have the same address if you removed : 1 from the declaration of bit, so you don't actually get a bit field.
    – Shahbaz
    Commented Jan 19, 2016 at 21:42
  • I tried your code like this: for (int i = 0; i < number_of_bits; ++i) bitstream[i].bit = i % 2; and later printing the bits looking at the memory's actual bit pattern: printf("%08X %08X %08X %08X\n", ((uint32_t *)bf)[0], ((uint32_t *)bf)[1], ((uint32_t *)bf)[2], ((uint32_t *)bf)[3]); The result was 00000000 00000001 00000000 00000001
    – Shahbaz
    Commented Jan 19, 2016 at 21:44
  • Thank you! I had tried this, and I should have mentioned that it is not useful for saving space, since the pointer size per struct will be the next available address. It is useful, however, if you are looking for the looping effect (1+1 becomes zero again). I will edit my post to mention the memory issue. Commented Jan 20, 2016 at 13:35
  • 1
    If this doesn't conserve memory, what's the point? We could just use bool[] in that case. Commented Jan 20, 2016 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.