If a 32-Bit Integer Overflows, How to Use a 40-Bit Structure Instead of a 64-Bit Long One

If a 32-bit integer overflows, can we use a 40-bit structure instead of a 64-bit long one?

Yes, but...

It is certainly possible, but it is usually nonsensical (for any program that doesn't use billions of these numbers):

#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
    uint64_t var : 40;
};

Here, var will indeed have a width of 40 bits at the expense of ~~much~~ less efficient code generated (it turns out that "much" is very much wrong -- the measured overhead is a mere 1-2%, see timings below), and usually to no avail. Unless you have need for another 24-bit value (or an 8 and 16 bit value) which you wish to pack into the same structure, alignment will forfeit anything that you may gain.

In any case, unless you have billions of these, the effective difference in memory consumption will not be noticeable (but the extra code needed to manage the bit field will be noticeable!).

Note:
The question has in the mean time been updated to reflect that indeed billions of numbers are needed, so this may be a viable thing to do, presumed that you take measures not to lose the gains due to structure alignment and padding, i.e. either by storing something else in the remaining 24 bits or by storing your 40-bit values in structures of 8 each or multiples thereof).

Saving three bytes a billion times is worthwhile as it will require noticeably fewer memory pages and thus cause fewer cache and TLB misses, and above all page faults (a single page fault weighting tens of millions instructions).

While the above snippet does not make use of the remaining 24 bits (it merely demonstrates the "use 40 bits" part), something akin to the following will be necessary to really make the approach useful in a sense of preserving memory -- presumed that you indeed have other "useful" data to put in the holes:

struct using_gaps
{
    uint64_t var           : 40;
    uint64_t useful_uint16 : 16;
    uint64_t char_or_bool  : 8;  
};

Structure size and alignment will be equal to a 64 bit integer, so nothing is wasted if you make e.g. an array of a billion such structures (even without using compiler-specific extensions). If you don't have use for an 8-bit value, you could also use an 48-bit and a 16-bit value (giving a bigger overflow margin).

Alternatively you could, at the expense of usability, put 8 40-bit values into a structure (least common multiple of 40 and 64 being 320 = 8*40). Of course then your code which accesses elements in the array of structures will become much more complicated (though one could probably implement an operator[] that restores the linear array functionality and hides the structure complexity).

Update:
Wrote a quick test suite, just to see what overhead the bitfields (and operator overloading with bitfield refs) would have. Posted code (due to length) at gcc.godbolt.org, test output from my Win7-64 machine is:

Running test for array size = 1048576
what       alloc   seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      2       1       35       35       1
uint64_t    0      3       3       35       35       1
bad40_t     0      5       3       35       35       1
packed40_t  0      7       4       48       49       1

Running test for array size = 16777216
what        alloc  seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      38      14      560      555      8
uint64_t    0      81      22      565      554      17
bad40_t     0      85      25      565      561      16
packed40_t  0      151     75      765      774      16

Running test for array size = 134217728
what        alloc  seq(w)  seq(r)  rand(w)  rand(r)  free
-----------------------------------------------------------
uint32_t    0      312     100     4480     4441     65
uint64_t    0      648     172     4482     4490     130
bad40_t     0      682     193     4573     4492     130
packed40_t  0      1164    552     6181     6176     130

What one can see is that the extra overhead of bitfields is neglegible, but the operator overloading with bitfield reference as a convenience thing is rather drastic (about 3x increase) when accessing data linearly in a cache-friendly manner. On the other hand, on random access it barely even matters.

These timings suggest that simply using 64-bit integers would be better since they are still faster overall than bitfields (despite touching more memory), but of course they do not take into account the cost of page faults with much bigger datasets. It might look very different once you run out of physical RAM (I didn't test that).

Which C datatype can represent a 40-bit binary number?

If you're using a C99 or C11 compliant compiler, then use int_least64_t for maximum compatibility. Or, if you want an unsigned type, uint_least64_t. These are both defined in <stdint.h>

<stdint.h> usually also defines int64_t, but since it's not required by the standard, it may not be defined in every implementation. However:

int_least64_t - at least 64 bits, and
int_fast64_t - the fastest size in this implementation of at least 64 bits

are both required to be present in C99 and C11 (See § 7.18.1.2-3 in the C99 standard, and § 7.20.1.2-3 in the C11 standard).

Although C99 specifies that long long is at least 64 bits on a particular machine (§ 5.2.4.2.1), the types in <stdint.h> are designed to be explicitly portable.

You can read more about integer sizes on different platforms here.
Note that the size of integer types are a problem with the long data type - on 64 bit Windows, it's currently 32 bits, whereas on 64 bit linux it's 64 bits. For this reason, I believe you're safest using the types from <stdint.h>

It's worth noting that some feel that long long is more readable. Personally, I prefer the types from <stdint.h>, because they allow you to say what you mean when you use them - which I find more readable. Of course, readability is often a matter of taste - and if you're working with an existing codebase, I'd just follow whatever they do :)

If your compiler only supports C89, then R..'s solution will allow you up to 53 bits of integer precision.

How to convert a 48-bit byte array into an 64-bit integer in C?

A C99 implementation may offer uint64_t (it doesn't have to provide it if there is no native fixed-width integer that is exactly 64 bits), in which case, you could use:

#include <stdint.h>

unsigned char data[6] = { /* bytes from somewhere */ };
uint64_t result = ((uint64_t)data[0] << 40) |
                  ((uint64_t)data[1] << 32) |
                  ((uint64_t)data[2] << 24) |
                  ((uint64_t)data[3] << 16) |
                  ((uint64_t)data[4] << 8)  |
                  ((uint64_t)data[5] << 0);

If your C99 implementation doesn't provide uint64_t you can still use unsigned long long or (I think) uint_least64_t. This will work regardless of the native endianness of the host.

How can i use 6 byte integer data type in C?

There is a way to have exact number of bits for something in C, so in theory it's doable, but it will take more than 48 bits in memory.

To do so you can use bit fields from C, to do so you can:

struct your_type {
   uint64_t your_value : 48;
};

With this you can create such struct, and access your_value which will have 48 bit representation. It will be treated as uint64_t under the hood.

Saying that I strongly recommend reading Ansi C or any other basic C book to get to know basics better.

Please mind that creating parsers with bitfields is generally bad idea due to padding, packing and endianess issues issues. If you need to have any protocol please take interest in messagepack or any other protocol library.

Performance of 32-bit integers in a 64-bit environment (C++)

I think you have a huge case of pre-mature optimization staring you in the face. Never make micro changes like this in your application until a profiler has definitively told you that it is a source of significant performance problems.

Otherwise you'll spend a lot of time fixing non-problems.