Calculate n % 12 [closed]

Question

Calculate n modulo 12 for an unsigned 32 bit integer.

The Rules:

• Must work for all n between 0 and 23. Other numbers optional.
• Must only use any of the operators +-*, ~&^| or <<, >> as commonly defined on 32 bit uints.
• May use arbitrary number of constant uints.
• May not use any form of pointers, including arrays, or any if statements, including things that compile to if statements such as ternary operators or "greater than" operators.

The scoring:

• Operators + - and the bitwise operators ~ & ^ | << >> (NOT, AND, XOR, OR, bit shifts) give a score of 1, * gives a score of 2.
• Lowest total score wins.

Answer 1

4

(Language is irrelevant)

n-((48&(11-n))>>2)

Woo! Got to 4.

11-n will ensure all of the high order bits are set if and only if n>= 12.

48&(11-n) == if n>11 then 48 else 0

(48&(11-n))>>2 == if n>11 then 12 else 0

n-((48&(11-n))>>2) is the answer

Answer 2

4

A solution with a lookup table (it looks up i ^ (i % 12)):

i ^ (0x1d4c000 >> (i & 0xfc) & 30)

4

Here's another solution with 4 operations:

i - ((0xffff >> (i - 12)) & 12)

It assumes that the count operand of bitshifts is implicitly taken mod 32, i.e. x >> -1 is the same as x >> 31.

5

Another approach, using a lookup table:

i - (16773120 >> i & 1) * 12

Answer 3

bash – 1

echo `seq 0 11` `seq 0 11` | awk '{print $(number+1)}'

e.g.

$ echo `seq 0 11` `seq 0 11` | awk '{print $(0+1)}'
0

$ echo `seq 0 11` `seq 0 11` | awk '{print $(11+1)}'
11

$ echo `seq 0 11` `seq 0 11` | awk '{print $(12+1)}'
0

$ echo `seq 0 11` `seq 0 11` | awk '{print $(23+1)}'
11

Answer 4

C, little-endian - 2

This is probably cheating but I think it satisfies the rules...

union {
    int i;
    struct {
        int a:4;
        int b:2;
        int c:10;
    } s;
    struct {
        int a:2;
        int b:14;
    } t;
} u;

u.i = 11-n;
u.s.a = 0;
u.s.c = 0;
result = n-u.t.b;

Answer 5

PHP - score 0

I wonder how is it possible that noone came with this before me!!!

$n = 18;
$s = str_repeat("a", $n);
$s2 = preg_replace('/aaaaaaaaaaaa/', '', $s);
echo strlen($s2);

Answer 6

C, score 5

Works up to 23, not guaranteed above that.

( ((n+4)>>2)&4 ) + n & 15

((n+4)>>2)&4 returns 4 for n>=12. Add it to n and you get the right answer in the least significant 4 bits, then truncate the other bits.

Answer 7

whatever language: 5

not going to win, but participating because fun and maybe because it's easier to understand then others:

n - ((n+20)>>5)*12

this is equivalent to

n - (n>11)*12

this is equivalent because when you add 20 to 12, you get 32, thus the 5th bit becomes 1. This is only when n > 1 as 32 is the smallest number where the 5th bit becomes 1.

also note that is easily expandable for a higher range, as you can do

n - ((n+20)>>5)*12 - ((n+41)>>5)*12

to reach a range until 35

Answer 8

Python 2.x - 4

j=input();m=lambda a,b:a*b;a=(m(j,357913942)>>32);print j-m(12,a)

Is = an operator?

In that case the score is 6.

j-12*(j*357913942>>32)

BTW @steveverrill 's solution can be directly used in Python as well.

Works for the range 0 .. 23

So whats going on ? Multiply by 357913942 and divide by 2^32 (or right shift 32)

Answer 9

C - 6

(n - (((n * 0xAAAB) >> 19)) * 12 )

Answer 10

Cobra - 2 (or 3)

def modulo12(n as uint32) as uint32
        for i in 11:n to int64:12,n-=12
        return n

This might be bending the rules a bit, but I've asked and was allowed to use this.

It also works for any number.

Answer 11

Kona - 5

Might be invalid because I'm not sure if the floor operator is allowed, but I've got two * and a minus:

mod:{x-(_0.08333*x)*12}

Which should work for any integer.