2

I've been trying to search this specific answer here on SO and other websites, but I haven't got any clear answer so far.
Is it possible to find the last digit of an integer as of x % 10 using bitwise operators?

In my code I have something like rand() % 10 and I wanted to know if is there anything I could to make it as a bitwise operation, in fewer lines possible.

I know that if you have an hexadecimal number, you can do this by the following:
0xABCDE & 0xF == E
0xABCD & 0xF == D
and so on...
However, this would result in a range bigger than 10. Since I'm using a random number generator, I would like to have all these operations in the range from 0 to 9. Is that possible?

thevoyager
  • 33
  • 5
  • 6
    Have a look at http://homepage.cs.uiowa.edu/~jones/bcd/mod.shtml#exmod10 – Jerry Jeremiah May 08 '23 at 04:37
  • 3
    1. Why does the modulo operator hurt you? -- 2. Let's pretend for a moment that such a bitwise operator exists and let's define it as `#`. Please [edit] your question and show the existing and the new expression in its complete statement. Currently I fail to see how `value % 10` can be expressed shorter. – the busybee May 08 '23 at 06:06
  • @thebusybee I think by "in fewer lines possible", OP means "in as few lines as possible". The motivation might have to do with speed, or perhaps they are asking to see whether one can implement this in the hardware using bit logic. – Lover of Structure May 08 '23 at 07:06
  • @LoverofStructure Thanks, that is most probably the right interpretation, anyway, it is speculation. Therefore, the OP needs to clarify. ;-) We don't even have a clue what target hardware is used. – the busybee May 08 '23 at 07:19
  • 3
    3. The more I think about your problem, the more I feel that this is an [XY problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). What issue do you really want to solve? – the busybee May 08 '23 at 07:21
  • 1
    @JerryJeremiah The function mod10() you linked to doesn't work correctly. It fails first at 510. – Simon Goater May 08 '23 at 12:13
  • 5
    Please note that compilers are optimizing your code for you, and they often know best which sequence of instructions to use under the hood to get the result you want. They know how to optimize multiplications and divisions by constants. So I would just write `value % 10` in your code and trust the compiler to do what is best. Note that that still might be a simple division instruction, if that is faster than multiple bitwise instructions. On x86_64, GCC turns the modulo 10 into a multiplication followed by some shift, add and sub instructions: https://godbolt.org/z/qPdcxz5fT – G. Sliepen May 08 '23 at 12:38
  • Looks like an XY problem to me. Why do you think you need to replace `%` with bitwise operators? Note that `rand() % 10` does not produce an uniform distribution, and any replacement that does the same thing with bitwise operators won't either. If you need a uniform distribution, you need an algorithm that produces a uniform distribution, which `rand() % 10` isn't. If you do *not* need a uniform distribution, consider returning `4` every time. – n. m. could be an AI May 09 '23 at 15:41
  • 1
    One very simple algorithm that produces a uniform distribution in `[0..9]` (assuming `rand()` is uniform and ranges from 0 to 2^k-1) is like that: `int x; while ((x = rand() & 0xF) >= 10; return x;` (and it doesn't use `%`). – n. m. could be an AI May 09 '23 at 15:45
  • @n.m. Worrying about distribution of random numbers from `rand()` is a bit like finding a rusted-out Yugo in a junkyard and spending half a day waxing it. :-) If you're worried about cryptographic security you wouldn't be using `rand()` in the first place. If you have enough random bits, even `%` will be *de facto* cryptographically secure if the modulo is small - good luck getting information from the bias in `x` from `uint64_t x = getCryptoSecureRandom64(); x = x % 10;`. – Andrew Henle May 14 '23 at 13:32
  • @AndrewHenle `rand()` is a specification. There are some bad implementations out there, or perhaps all of them are bad, but I am not talking about implementations. – n. m. could be an AI May 14 '23 at 14:19
  • @AndrewHenle: Uniform distribution and cryptographically secure are different properties. Uniform distribution may be desired simply to avoid skewing results of a study even when no concern about cryptographic security is present. – Eric Postpischil May 14 '23 at 14:32
  • technically yes, because all the operations are actually bitwise under the hood. But realistically not because it can be much slower than other methods like multiplication by the multiplicative inverse. See [fast division/mod by 10^x](https://stackoverflow.com/q/2033210/995714) – phuclv May 15 '23 at 03:44
  • Just a nostalgic note: x86 processors still support instructions for BDC arithmetics, like DAA. It had helped me in some limited case (e.g. small numbers) by some bitmasking trick, at the old age of MSDOS. But it does not scale well, and anyway on x64 it is no longer supported. As far as I know, there is nothing similar on different architectures. – Giuseppe Guerrini May 15 '23 at 11:23
  • 2
    @GiuseppeGuerrini As I recall, it was not uncommon to have BCD support in the old days (1980's). I think both the Z80 and 6502 had support for BCD arithmetics. – nielsen May 15 '23 at 11:56
  • 1
    @nielsen Correct. I should have written "there is nothing similar on modern architectures" :-) – Giuseppe Guerrini May 15 '23 at 12:29

4 Answers4

4

Is it possible to make x%10 with bitwise operators in C?

No, not reasonably.

It's well known that if N is a power of 2, x%N can be efficiently computed by using a bitmask. (For example, x%16 is x & 0x0F, at least as long as x is unsigned.) And in fact, this is so well known that virtually any C compiler knows how to do it, too.

Given the appealing efficiency and economy of power-of-2 moduli, it's tempting to look for similar tricks for other divisors. Unfortunately, the math doesn't work out. As this question's other answers show, while you can technically compute x%10 using elaborate combinations of bitwise operators, it's not at all clear that there's any value to the exercise. See also Fast division/mod by 10x.

At the end of the day, if you want to compute x%10, the best way to express it in C is as the wholly unmagical but blatantly obvious:

x % 10

If there's a better way to implement it than actual division, leave it to the compiler to make the optimization for you. And the code remains obvious, because everyone knows what x % 10 means.

(And, indeed, even though I just said I didn't think there was a reasonable "bitwise shortcut" for computing x % 10, it turns out that gcc, at least, does tend to compile that particular expression down to a cryptic and presumably more-efficient sequence of multiplications, additions, and shifts, without any DIV instructions at all.)

If computing x%10 is proving to be a bottleneck in your program, it's appropriate to ask, why are you computing x%10 so much, and is there a better alternative?

You mentioned that you had "something like rand() % 10", as if you're generating individual, random, decimal digits. If that's fundamentally what you need to do, there may not be a better way. You're wasting a lot of the entropy that rand() is trying to give you, though. You might want to consider a special-purpose random number generator. Or if you're assembling your individual random digits into larger numbers, you might want to consider generating those larger numbers more directly.

Another place where x%10 comes up a lot, of course, is when converting a number to its decimal representation. For example, I once wrote an arbitrary-precision arithmetic library, and it works internally in binary, and when it has to convert one of its bignums into decimal to print it out, it can take a noticeable amount of time. Adjusting the library to use a decimal representation internally lets it print things in decimal much more efficiently. (Of course, it makes certain other operations significantly less efficient.)

If you're converting numbers to decimal as part of a serialization format, and if there's no requirement for the serialization format to be easily humanly readable, you might consider serializing integers in hexadecimal rather than decimal, because in that case the conversion will involve a bunch of computations of x%16 instead of x%10.

Steve Summit
  • 45,437
  • 7
  • 70
  • 103
0

Does this count? No loops, no conditionals, just &, >>, and array indexing. For 64-bit support, make the function twice as long.

int mod10(unsigned int n) {
    const int tab[2][10] = {
        { 0, 2, 4, 6, 8, 0, 2, 4, 6, 8 },
        { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9 },
    };
    
    return tab[n & 1][
      tab[(n >> 1) & 1][
      tab[(n >> 2) & 1][
      tab[(n >> 3) & 1][
      tab[(n >> 4) & 1][
      tab[(n >> 5) & 1][
      tab[(n >> 6) & 1][
      tab[(n >> 7) & 1][
      tab[(n >> 8) & 1][
      tab[(n >> 9) & 1][
      tab[(n >> 10) & 1][
      tab[(n >> 11) & 1][
      tab[(n >> 12) & 1][
      tab[(n >> 13) & 1][
      tab[(n >> 14) & 1][
      tab[(n >> 15) & 1][
      tab[(n >> 16) & 1][
      tab[(n >> 17) & 1][
      tab[(n >> 18) & 1][
      tab[(n >> 19) & 1][
      tab[(n >> 20) & 1][
      tab[(n >> 21) & 1][
      tab[(n >> 22) & 1][
      tab[(n >> 23) & 1][
      tab[(n >> 24) & 1][
      tab[(n >> 25) & 1][
      tab[(n >> 26) & 1][
      tab[(n >> 27) & 1][
      tab[(n >> 28) & 1][
      tab[(n >> 29) & 1][
      tab[(n >> 30) & 1][
      (n >> 31) & 1]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]];
}

Please note there is absolutely no reason to ever use this code, but it does work, and it may be worthwhile to understand it.

The working principle is that tab[a][b] equals (2*b + a) % 10. Another way to look at it is that we're taking 32 steps through a DFA, starting at state 0, and each state has two arrows: arrow 0 leads to (2*n)%10, and arrow 1 leads to (2*n+1)%10. The final state is the result.

hobbs
  • 223,387
  • 19
  • 210
  • 288
0

I came up with this which works, but there is probably a more elegant way to do it. Using a look-up table seems a bit like cheating, but I don't know how to get rid of the last few multiples of 10 without branching and looping etc. Anyway, it might be of interest to someone.

A 64 bit version could be constructed similarly but instead I've opted to play safe and have 64bit function which calls the 32 bit function for which all input values have been checked.

uint32_t uint32mod10(uint32_t n) {
/*
n = sum_{i=0 to 7} (2^4i)n_i
n % 10 = (n_0 + 6(sum_{i=1 to 7} n_i)) % 10

n = sum_{i=0 to 9} (2^i)b_i
n % 10 = (b_0 + 2(b_1 + b_5 + b_9) + 4(b_2 + b_6) + 8(b_3 + b_7) + 6(b_4 + b_8)) 
*/
  uint8_t lut[44] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    0, 1, 2, 3};
  uint32_t m = ((n >> 4) & 0xf) + ((n >> 8) & 0xf) + ((n >> 12) & 0xf) + ((n >> 16) & 0xf)
    + ((n >> 20) & 0xf) + ((n >> 24) & 0xf) + ((n >> 28) & 0xf); // max 7*15 = 105
  n = (n & 0xf) + (m << 2) + (m << 1); // max 15 + 630 = 645
  m = ((n & 0x10) >> 3) + ((n & 0x100) >> 7);
  n = (n & 0xf) + ((n & 0xe0) >> 4) + (m << 1) + m
    + ((n & 0x200) >> 8); // max 15 + 14 + 12 + 2 = 43
  return lut[n];
}


uint32_t uint64mod10(uint64_t n) {
  /*
n = n_0 + n_1*2^24 + n_2*2^48
n % 10 = (n_0 + 6(n_1 + n_2)) % 10 
  */
  uint64_t m = (n >> 48) + ((n >> 24) & 0xffffff);
  return uint32mod10((uint32_t)((n & 0xffffff) + (m << 2) + (m << 1)));
}

EDIT:

Something probably easy to code on a microcontroller which could actually be extended for use for binary to decimal conversion for 32bit unsigned integers is as follows.

static inline uint32_t uint32divby5(uint32_t n) {  
  uint32_t a, m = (n >> 2) - (n >> 4);
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  m = (n - m) >> 2;
  a = m + (m << 2);
  if (a > n) return m - 1;
  return m;
}

uint32_t uint32mod10b(uint32_t n) {
  uint32_t m = uint32divby5(n >> 1);
  return n - (m << 3) - (m << 1);
}

EDIT2:

Another alternative if 64bit arithmetic is available,

static inline uint32_t fastdiv16(uint16_t denom, uint32_t lp30, uint64_t m, uint32_t num)  {
  //result = num/denom
  //uint64_t m = (((uint64_t)1 << 63) / denom);
  //uint32_t lp30 = 30 + lzcnt(m);
  //m = m >> (63 - lp30);
  uint64_t q = (num  * m) >> lp30;
  uint64_t test = q*denom;
  return (uint32_t)(q + 1 - (test + denom > num));
}


uint32_t uint32mod10c(uint32_t n) {
  uint32_t m = fastdiv16(10, 34, 1717986918, n);
  return n - (m << 3) - (m << 1);
}
Simon Goater
  • 759
  • 1
  • 1
  • 7
0

For a number in the range of 0-99 you can use:

x - (10*((x*103)>>10)

It's not strictly bit operations, and it's questionable if it would be faster than a remainder operation.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622