Get random bit off the end of a float

Question

I have a float in my program that changes after each iteration, namely G[0]. I want to use the last bit of the mantissa as a "random" bit that I will use to pick which path to take in my computation. However, the calculation I'm using now always prints out 0, while it should be roughly 50/50; what's my error? The function signature defines float* G.

unsigned rand_bit = *((unsigned *)&G[0])>>31;
printf("%i", rand_bit);

a) A float is only 32 bits long. After you shift it over 32 bits what do you think is left? b) Are you sure you know in which bit the "last" bit of the mantissa is in? — davidbak, Jul 11 '16 at 23:10
a) Thanks, sorry b) Yes, I looked at the IEEE specification; it goes sign, exponent, mantissa. — Elliot Gorokhovsky, Jul 11 '16 at 23:11
Oh wait! That answers my question, doesn't it... I'm always getting the sign bit! I need to reverse it before shifting... how does one do that? Or generally how does one get the *rightmost* bit? I'm getting the leftmost. — Elliot Gorokhovsky, Jul 11 '16 at 23:11
Oh ya, that would be way better.... I'll accept that answer. I need to do `G[0] && 1` basically. — Elliot Gorokhovsky, Jul 11 '16 at 23:13
Yes ... but only on a little endian architecture (like x86, x64) of course. — davidbak, Jul 11 '16 at 23:13
Are GPUs little-endian? I'm running this on openCL. Using pyopencl. Hence utter ignorance of bitwise hacks. I'm a python programmer. — Elliot Gorokhovsky, Jul 11 '16 at 23:14
Don't know! I'll have to look that up! (Anyway, you can easily run an experiment ...) — davidbak, Jul 11 '16 at 23:14
Probably nothing... as I said, I don't really know C. I'll accept that answer. — Elliot Gorokhovsky, Jul 11 '16 at 23:16
In C, given a pointer `p`, `*p` and `p[0]` refer to the same location. Because `*(p+n)` and `p[n]` are exactly the same. — davidbak, Jul 11 '16 at 23:19
@RenéG: probably best to just close the question - it is mostly a localised issue (you made a simple logic error that means your question of "why is the last bit always 0", not valid). This question doesn't help anyone else. — dave, Jul 11 '16 at 23:47
@davidbak: `(unsigned)(G[0])` *converts* the first element of `G` to `unsigned` (which is well-defined if G[0] is non-negative and not too big). If `G[0]` is an IEEE-754 `float` and larger than 2^23, then the low-order bit of the converted value is guaranteed to be 0. `*(unsigned*)(G)`, on the other hand, *reinterprets* the first element of `G` as an `unsigned`. That is undefined behaviour, but on normal IEEE-754 hardware, it will do what OP wants. — rici, Jul 12 '16 at 00:33
@rici well, it would if it weren't a strict aliasing violation — M.M, Jul 12 '16 at 01:47

score 1 · Answer 1 · answered Jul 12 '16 at 00:41

Although you actual problem got solved I want to propose to use a union instead, it is a bit cleaner, but I do not know what is faster (if you are using the GPU I think I can safely assume that you want it fast). Endianness is also a problem; I was not able to find much information in that direction regarding GPUs, so here are some lines you might want to use.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int last_bit(float f)
{
  // Endianness testing should be done at compile-time, such that a simple macro
  // would suffice. Your compiler/libc might already offer one for that
#ifdef USE_TYPE_PUNNING
  // So called "type punning" is frowned upon by some
  uint32_t ui = 0x76543210;
  unsigned char *c = (unsigned char *) &ui;
#else
  union {
    uint32_t ui;
    uint8_t uc[4];
  } end = {0x76543210};
  // only to save some code branching, end.uc can be used directly, of course
  unsigned char *c = (unsigned char *) end.uc;
#endif
  int rand_bit;

  union {
    float fl;
    uint32_t ui;
  } w;

  w.fl = f;
#ifdef DEBUG
  printf("%x\n", w.ui);
#endif
  // Little endian
  if (*c == 0x10) {
    rand_bit = w.ui & 0x1;
  }
  // Big endian
  else if (*c == 0x76) {
    rand_bit = w.ui & 0x1;
  }
  // Too old/new
  else {
    fprintf(stderr, "unknown endianness\n");
    return -1;
  }
  return rand_bit;
}


int main(int argc, char **argv)
{
  float f;

  // all checks omitted!
  if (argc >= 2) {
    f = atof(argv[1]);
  } else {
    // 0x40e00000 even
    //f = 7;
    // 0x3f8ccccd odd
    f = 1.1;
  }
  printf("last bit of mantissa = %d\n", last_bit(f));
  exit(EXIT_SUCCESS);
}

Endianness should not matter, **unless** int and float have a different one. that is pretty seldom, though. — Rudy Velthuis, Jul 12 '16 at 01:52

score 1 · Accepted Answer · edited May 23 '17 at 12:08

First of all, *((unsigned *)&G[0]) causes undefined behaviour by violating the strict aliasing rule. In Standard C it is not permitted to access memory of one type by using a different type, except for a handful of special cases.

You can fix this either by disabling strict aliasing in your compiler, or using a union or memcpy.

(Also your code is relying on unsigned being the same size as float, which is not true in general).

But supposing you did fix those issues, your code is testing the most-significant bit. In the IEEE 32-bit floating point format, that bit is the sign bit. So it will read 0 for positive numbers and 1 for negative numbers.

The last bit of the mantissa would be the least significant bit after reinterpreting the memory as integer.

Corrected code could look like:

unsigned u;
assert( sizeof u == sizeof *G );
memcpy(&u, G, sizeof u);
printf("%u", u & 1);

NB. I would be hesitant about assuming this bit will be "random", if you want a random distribution of bits there are much better options.

Get random bit off the end of a float

2 Answers2