18

I want to know how bitset actually allocates memory. I read from some blog that it takes up memory in bits. However when i run the following code: 

   bitset<3> bits = 001;
   cout<<sizeof(bits);

I get the output as 4. What is the explanation behind it?

Also is there a method to allocate space in bits in C++?

Saurabh
  • 333
  • 1
  • 2
  • 11
  • 13
    You cannot allocate space in bits, since that’s not how the C++ abstract machine works. Just like you cannot buy half of a banana in a supermarket, you cannot allocate half bytes. –  Sep 17 '12 at 12:52
  • I just want to know the allocation mechanism behind it. Like when you declare a static array of N size, you know it will take 4*N bytes. So how such a thing can be done with bitset? – Saurabh Sep 17 '12 at 12:54
  • 1
    It will round up to the least amount of bytes it takes to store N bits, *at least*. The compiler will add alignment and stuff to make accessing the data faster, but how it does that exactly is implementation-defined. –  Sep 17 '12 at 12:55
  • 2
    "Also is there a method to allocate space in bits in C++?", yes, but you can only allocate 8 of them at a time... – Luchian Grigore Sep 17 '12 at 12:56
  • 3
    @LuchianGrigore not always 8; it depends on `CHAR_BIT`. –  Sep 17 '12 at 12:56
  • @daknøk talk about pedantry... – Luchian Grigore Sep 17 '12 at 12:57
  • 3
    @LuchianGrigore s/pedantry/correctness/ –  Sep 17 '12 at 12:57

5 Answers5

15

You can approximate sizeof(bitset<N>) as:

  1. If internal representation is 32bit (like unsigned on 32bit systems) as 4 * ((N + 31) / 32)
  2. If internal representation is 64bit (like unsigned long on 64bit systems) as 8 * ((N + 63) / 64)

It seems that the first is true: 4 * ((3 + 31) / 32) is 4

PiotrNycz
  • 23,099
  • 7
  • 66
  • 112
  • Can you elaborate why it is `(N + 31) / 32`? Thx. – Deqing Sep 16 '13 at 08:00
  • @Deqing This the way how ceiling value could be evaluated for some Numberator/Denominator expression in integers. To get ceil(N/D) - you need to use this expression: (N + D - 1) / D. See: 31==32-1. I need ceiling value of N/32 so I use this trick to get it... – PiotrNycz Nov 06 '13 at 15:30
  • 1
    the formula `4 * ((N + 31) / 32)` worked for me for n = 3,40 but then failed when n = 66. It seems, there is no deterministic formula here... – daparic Jul 16 '18 at 14:05
  • @ifelsemonkey - do you mean `sizeof(std::bitset<66>)` is not `4 * (66+31)/32` which is 12? Maybe above some number (like 66) - "your" bitset internally changes to `uint64_t[]` array - so its size is `8 * (66+63)/64` which is 16 ? – PiotrNycz Jul 16 '18 at 16:23
  • @ifelsemonkey - anyway - we cannot 100% predict the size of bitset - since its internal representation can change just because new version of std library selects other internal representation. So my answer is only approximation of real value (I used this verb). – PiotrNycz Jul 16 '18 at 16:30
8

I get the output as 4. What is the explanation behind it?

There is no information in standard about how bitset should be realized. It's implementation defined, look at bitset header of your compiler.

Also is there a method to allocate space in bits in C++?

No, there is no method to allocate space in bits in C++.

ForEveR
  • 55,233
  • 2
  • 119
  • 133
8

Your CPU doesn't operate with individual bits, but with bytes and words. In your case, sizeof(bits) results in 4 because compiler decided to align this datastructure to 4 bytes.

Juho
  • 983
  • 5
  • 9
1

Typically on a 32-bit processor, the compiler will make the allocated memory size a multiple of 4 bytes, and so the nearest multiple of 4 greater than 3/8 is 4 bytes.

jrtc27
  • 8,496
  • 3
  • 36
  • 68
0

You cannot address separate bits, the lowest adressable unit is byte. So no, you cannot allocate bits precisely.

Another thing is padding - you almost always get more bytes allocated that you asked for, this is for optimalization purposes. Addressing bytes not on 32b boundaries is often expensive, addressing bytes on x64 CPU that are not on 64b boundaries results in exception. (speaking of Intel platform.)

nothrow
  • 15,882
  • 9
  • 57
  • 104