Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.
share|improve this question
4  
You might want to define the operators for users of languages other than C/Java. I understand +-* are add, subtract, multiply; ~&^| are bitwise NOT,AND,XOR,OR; and << >> are bitshifts. –  steveverrill Jun 20 at 0:52
    
@steveverrill - thanks. That is indeed the intention. –  nbubis Jun 20 at 0:53
    
Can I use for i in x:y:z, .dostuff? –  Ourous Jun 20 at 1:43
    
Can I set a variable equal to a value to use in a expression? –  xnor Jun 20 at 2:42
3  
most compilers will optimize n % 12 to a multiplication and a shift like in hacker's delight, so this is trivial, just output the assembly and see –  Lưu Vĩnh Phúc Jun 20 at 6:42

13 Answers 13

up vote 23 down vote accepted

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

share|improve this answer
1  
Aww shucks, you beat me to this approach! I was only moments away from posting n - (((11 - n) & 0xC0000000) >> 28). Well done, I don't think it can be done in less than four. –  Runer112 Jun 20 at 3:01
1  
@Runner112 Yeah, I was hoping no one would beat me to it as I posted it. Well done on finding it for yourself, though –  isaacg Jun 20 at 3:03
1  
Awesome :) 4 is indeed an accomplishment. –  nbubis Jun 20 at 5:19

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
share|improve this answer

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
share|improve this answer
    
+1.000000001 - THIS IS EVIL! I LIKE IT! –  vaxquis Jun 21 at 2:28
1  
This isn't valid because it uses pointers. –  curiousdannii Jun 21 at 4:56
    
@curiousdannii What pointers are you referring to? The stdin and stdout streams? Sure, internally, they are pointers, but then we might as well disqualify Java because it uses the Integer class internally for a lot of things. –  Cole Johnson Jun 21 at 18:31
    
Isn't $() effectively equivalent to a pointer? –  curiousdannii Jun 21 at 23:32
    
@curiousdannii - awk documentation says they're built-in variables. –  Yimin Rong Jun 22 at 8:44

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;
share|improve this answer
    
How does it work? –  nbubis Jun 20 at 18:55
1  
Sorta cheating, since you're using = 0 instead of & 0x0, which should count as an additional 2 operations. But +1 for the creativity :) –  nbubis Jun 20 at 19:03

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);
share|improve this answer
1  
Nice. I think there may be an issue though, since arrays are disallowed. Really nice though. –  AJMansfield Jun 22 at 2:03
    
@AJMansfield One could argue this doesn't have arrays but strings (yes, at low level strings are byte arrays). :) –  Sieg Jun 22 at 17:24

3

Edit: This breaks the rules in using more than 32 bits.

I wrote this in Python, though any language should do. The key is to use a huge lookup table. The idea generalizes to get a score of 3 for any function with a bounded set of inputs.

(0xBA9876543210BA9876543210>>(n<<2))&15

Here are the parts:

0xBA9876543210BA9876543210

The lookup table for the answer. If read right to left in blocks of four, has the numbers from 0 to 11, then the numbers 0 to 11 again. So, hex digit n from the end is n%12.

n<<2

Multiply n by 4.

(0xBA9876543210BA9876543210>>(n<<2))

Shift the constant 4*n binary blocks (equivalently n hex digits) to the right, which puts the answer in the righmost block.

&15

Take the rightmost four binary digits, which is the last hex digit, to get the result.


In the same general way, if f(n) needs to be evaluated for n = 0 to N-1, one can compute f in 3 operations as (c>>(n<<k))&&(2**k-1) with c being constant obtained by the binary concatenation f(N-1)f(N-2)...f(1)f(0) with each block padded to a sufficiently contant large length k with 2**k>f(n).

share|improve this answer
1  
The table is more than 32 bits, so the right shift lookup is not among the allowed operations. –  Potatoswatter Jun 21 at 8:14
    
Well done, though as @Potatoswatter pointed out, this needs a 96 bit integer, which is not really supported on most languages, nor by the rules :) –  nbubis Jun 21 at 19:00

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.

share|improve this answer
    
Well done!! Now let's see if someone can get to 4.. –  nbubis Jun 20 at 0:48

J - score of 2

This is cheating, so this answer isn't competing. % is in fact division in J.

f =: 12&|

This would translate to f(n) = n mod 12

share|improve this answer
    
If it's not competing, why not Community Wiki it? –  Kyle Kanos Jun 20 at 13:59
    
@KyleKanos Forgot it existed. Changing –  Sieg Jun 20 at 14:28
    
Seems like people don't share my sense of humor. –  Sieg Jun 20 at 14:40
    
I've been fortunate to avoid the DV's for my answer that more-or-less was pointing out that the puzzle is a little underspecified. Have a +1 just to get a 0 score ;) –  Kyle Kanos Jun 20 at 14:41
1  
Because J is common language (especially common in code golf), its vocabulary is commonly defined. The question allows & and | as commonly defined, so this is a correct answer. –  kernigh Jun 20 at 14:52

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

share|improve this answer

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)

share|improve this answer
    
I like how you used a function to multiplicate only once. but imho you just renamed multiplication to the function m(,), which for me means you used it twice. –  Pinna_be Jun 20 at 20:27
    
depends how the rules are interpreted, but you have a valid point –  willem Jun 21 at 4:38

C - 6

(n - (((n * 0xAAAB) >> 19)) * 12 )
share|improve this answer
    
This should either be part of the question or just another answer. I suggest the latter. –  Jwosty Jun 20 at 1:12
    
@Jwosty - changed. –  nbubis Jun 20 at 23:16

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.

share|improve this answer

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.

share|improve this answer
    
I'm not sure about the floor operation, but I'm definitely sure that the first multiplication is operating on something other than 32-bit integers. –  Runer112 Jun 20 at 2:37
    
@Runer112: OP says input must be 32 bit and operators are as defined they normally are with 32 bit uints; it says nothing about non-integer values in the code. –  Kyle Kanos Jun 20 at 2:42
    
Unless I'm misunderstanding something, 0.08333*x doesn't seem like multiplication as defined on 32-bit uints, because 0.08333 is not a 32-bit uint. –  Runer112 Jun 20 at 2:47
1  
"May use arbitrary number of constant uints." - i.e. cannot use arbitrary floats. –  nbubis Jun 20 at 5:12
1  
@nbubis: that line does not actually put a restriction on floats. –  Kyle Kanos Jun 20 at 10:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.