roll.cpp

#include <random>
#include <iostream>
#include <vector>
#include <type_traits>
#include <inttypes.h>
#include <bitset>

enum ZeroBehavior {
  /// \brief The returned value is undefined.
  ZB_Undefined,
  /// \brief The returned value is numeric_limits<T>::max()
  ZB_Max,
  /// \brief The returned value is numeric_limits<T>::digits
  ZB_Width
};

template <typename T>
typename std::enable_if<std::numeric_limits<T>::is_integer &&
                        !std::numeric_limits<T>::is_signed, std::size_t>::type
countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
  (void)ZB;

  if (!Val)
    return std::numeric_limits<T>::digits;

  // Bisection method.
  std::size_t ZeroBits = 0;
  for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
    T Tmp = Val >> Shift;
    if (Tmp)
      Val = Tmp;
    else
      ZeroBits |= Shift;
  }
  return ZeroBits;
}

template <>
inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) {
  if (ZB != ZB_Undefined && Val == 0)
    return 32;
  return __builtin_clz(Val);
}

template <>
inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
  if (ZB != ZB_Undefined && Val == 0)
    return 64;
  return __builtin_clzll(Val);
}

inline unsigned Log2_32_Ceil(uint32_t Value) {
  return 32 - countLeadingZeros(Value - 1);
}

inline int roundUp(int numToRound, int multiple) 
{ 
 if(multiple == 0) 
 { 
  return numToRound; 
 } 

 int remainder = numToRound % multiple;
 if (remainder == 0)
  return numToRound;
 return numToRound + multiple - remainder;
}

int main(int argc, char **argv) {
  if (argc != 2) {
    std::cout << "roll number_of_friends\n";
    return EXIT_FAILURE;
  }
  
  unsigned num;
  try {
    num = std::stoul(argv[1]);
  } catch(...) {
    std::cout << "Failed to parse " << argv[1] << " as a number\n";
    return EXIT_FAILURE;
  }
  
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<unsigned> dis(1, 6);

  std::vector<unsigned> vals(num);
  
  // (x + y - 1) / y
  
  const unsigned num_bits = roundUp(Log2_32_Ceil(num), 2);
  const unsigned num_rolls = num_bits / 2;
  
  std::cout << "num bits: " << num_bits << "\n"
            << "num rolls: " << num_rolls << "\n";

  for (int n = 0; n < 1000000; ++n) {
    blah:
    unsigned val = 0;
    for (int i = 0; i < num_rolls;) {
      unsigned roll = dis(gen);
      if (roll > 4)
        continue;
      unsigned new_val = val | ((roll - 1) << (i * 2));
      if (new_val > num - 1)
        goto blah;
      val = new_val;
      ++i;
    }
    ++vals[val];
  }
  
  for (auto i : vals) {
    std::cout << i << "\n";
  }
}