1

So I'm trying to create an implementation of an algorithm that uses fixed-width integers. That being said I want to use the largest size available, and at the same time need to know the number of bits in it, as the algorithm relies on bit shifting.

I would like a way, preferably via pre-processor, to determine the width of the largest integer type (currently I'm using uintmax_t from stdint.h), but failing that I could exhaustively achieve this if I know the fixed-width types that are defined/supported by the compiler.

I found an old program on my PC where I have the pre-processor directives of #ifdef __INT64_TYPE__, which would be passable, but I have no idea where these would be defined, or under what standards.

So to sum up, if anyone knows a way to count the number of bits in uintmax_t, that'd be perfect, but failing that where have I got __INT64_TYPE__ from?

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
user163911
  • 169
  • 1
  • 4
  • 13
  • 2
    Have a look at the documentation: http://en.cppreference.com/w/c/types/integer – moooeeeep Feb 03 '16 at 18:11
  • An implementation is not required to provide any fixed-with integer types. State your target platform. – too honest for this site Feb 03 '16 at 18:16
  • @moooeeeep That's what I've been looking at, but they don't tell me where I got `__INT64_TYPE__` from, or anything regarding the width of `uintmax_t`. @Olaf I think implementation was a poor choice of words. I would like my answer to be portable yet as accurate as possible. – user163911 Feb 03 '16 at 18:20
  • In general, an algorithm is written for a specific precision. Thus you use a defined type. If you really have to optimise for speed, you have to adopt at leat parts to the platform anyway. Please state your actual problem. You might be working on a symptom. – too honest for this site Feb 03 '16 at 18:20
  • Do you really need the width as a constant expression in the preprocessing directive phase? If not, you could just use `#define UINTMAX_BITS ((sizeof(uintmax_t) * CHAR_BIT)` to determine the number of bits. – Ian Abbott Feb 03 '16 at 19:19
  • @Ian Abbott `((sizeof(uintmax_t) * CHAR_BITS)` works great unless on a rare platform that has padding bits in the type. – chux - Reinstate Monica Feb 03 '16 at 19:20
  • @Ian Abbot, I think you've prompted me to solve it. I needed a number that was `1 << NUM_BITS - 2`. I think `(UINTMAX_MAX >> 1) ^ (UINTMAX_MAX >> 2)` would work. I'm still relatively new to C, so I don't know if I'd run into any issues regarding this. – user163911 Feb 04 '16 at 13:43
  • If you're confident that `uintmax_t` has less than 2040 bits, you can (probably) use one of Hallvard's macros in [this answer](http://stackoverflow.com/a/4589384/) to calculate the number if bits at compile time. – Nisse Engström Feb 07 '16 at 17:18

2 Answers2

2

if anyone knows a way to count the number of bits in uintmax_t, that'd be perfect, but failing that where have I got INT64_TYPE from?

To count the number of bit in an unsigned type is easy. Set to -1 and count the number of shift until 0.

int bc_uintmax_t(void) {
  int bc = 0;
  uintmax_t x = -1;
  while (x) {
    x %= 2;
    bc++;
  }
  return bc;
}

To portable detect the number of bits in uintmax_t at compile time is harder. A chief obstacle is the pre-preprocessor arithmetic may only work up to intmax_t. So unless some assumptions are made, a portable solution may be unfindable.

Of course sizeof (uintmax_t) * CHAR_BIT is the maximum possible bit width that type could have. Yet padding bits could occur.

Look for (u)intmax_t and Exact-width integer types like uint64_t in <stdint.h>.

[Edit]

To determine the value bit width of a constant at compile time, code could use the following. Note: With UINTMAX_MAX, I am not certain how portable is this code.

#include <stdio.h>
#include <limits.h>

#define ISGE2_1(x)  ((x) >= 2)
#define ISGE2_2(x)  ((x) >= 4)
#define ISGE2_4(x)  ((x) >= 16)
#define ISGE2_8(x)  ((x) >= 256)
#define ISGE2_16(x) ((x) >= 65536)
#define ISGE2_32(x) ((x)/65536 >= 65536)
#define ISGE2_64(x) ((x)/4294967296 >= 4294967296)
#define ISGE2_128(x) ((x)/18446744073709551616 >= 18446744073709551616)

#define BW_1ORLESS(x)   ((x) ?  1 : 0)
#define BW_2ORLESS(x)   (ISGE2_1(x)  ?  1 + BW_1ORLESS(x/2)                     : BW_1ORLESS(x))
#define BW_4ORLESS(x)   (ISGE2_2(x)  ?  2 + BW_2ORLESS(x/4)                     : BW_2ORLESS(x))
#define BW_8ORLESS(x)   (ISGE2_4(x)  ?  4 + BW_4ORLESS(x/16)                    : BW_4ORLESS(x))
#define BW_16ORLESS(x)  (ISGE2_8(x)  ?  8 + BW_8ORLESS(x/256)                   : BW_8ORLESS(x))
#define BW_32ORLESS(x)  (ISGE2_16(x) ? 16 + BW_16ORLESS(x/65536)                : BW_16ORLESS(x))
#define BW_64ORLESS(x)  (ISGE2_32(x) ? 32 + BW_32ORLESS(x/4294967296)           : BW_32ORLESS(x))
#define BW_128ORLESS(x) (ISGE2_64(x) ? 64 + BW_64ORLESS(x/18446744073709551616) : BW_64ORLESS(x))


#if INTMAX_MAX/4294967296 > 4294967296
  #define BW_65PLUS(x) (ISGE2_128(x) ? BW_129PLUS(x) : BW_128ORLESS(x))
  #define BIT_WIDTH_POSITIVE_VALUE(x) (ISGE2_64(x) ? BW_65PLUS(x) : BW_64ORLESS(x))

#else
  #define BW_33PLUS(x) (ISGE2_64(x)   ? BW_65PLUS(x)  : BW_64ORLESS(x))
  #define BIT_WIDTH_POSITIVE_VALUE(x) (ISGE2_32(x) ? BW_64ORLESS(x) : BW_32ORLESS(x))
#endif

// Do not call BIT_WIDTH_POSITIVE_VALUE with negative values.

Application

#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>

int main() {
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(true));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(CHAR_BIT));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(SCHAR_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(SHRT_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(INT_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(LONG_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(LLONG_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(INTMAX_MAX));
  printf("%d\n", BIT_WIDTH_POSITIVE_VALUE(UINTMAX_MAX));
  return 0;
}

Output

1
4
7
15
31
31
63
63
64
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

I've used things like

#if (UINTMAX_MAX > 0xFFFFFFFFFFFFFFF5ULL)

etc.

Doug Currie
  • 40,708
  • 1
  • 95
  • 119