27
\$\begingroup\$

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.
\$\endgroup\$
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Level River St Jun 20 '14 at 0:52
  • \$\begingroup\$ @steveverrill - thanks. That is indeed the intention. \$\endgroup\$ – nbubis Jun 20 '14 at 0:53
  • \$\begingroup\$ Can I use for i in x:y:z, .dostuff? \$\endgroup\$ – Οurous Jun 20 '14 at 1:43
  • \$\begingroup\$ Can I set a variable equal to a value to use in a expression? \$\endgroup\$ – xnor Jun 20 '14 at 2:42
  • 4
    \$\begingroup\$ 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 \$\endgroup\$ – phuclv Jun 20 '14 at 6:42

11 Answers 11

29
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Runer112 Jun 20 '14 at 3:01
  • 1
    \$\begingroup\$ @Runner112 Yeah, I was hoping no one would beat me to it as I posted it. Well done on finding it for yourself, though \$\endgroup\$ – isaacg Jun 20 '14 at 3:03
  • 1
    \$\begingroup\$ Awesome :) 4 is indeed an accomplishment. \$\endgroup\$ – nbubis Jun 20 '14 at 5:19
11
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ This isn't valid because it uses pointers. \$\endgroup\$ – curiousdannii Jun 21 '14 at 4:56
  • \$\begingroup\$ @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. \$\endgroup\$ – Cole Johnson Jun 21 '14 at 18:31
  • \$\begingroup\$ Isn't $() effectively equivalent to a pointer? \$\endgroup\$ – curiousdannii Jun 21 '14 at 23:32
  • \$\begingroup\$ @curiousdannii - awk documentation says they're built-in variables. \$\endgroup\$ – Yimin Rong Jun 22 '14 at 8:44
5
\$\begingroup\$

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

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);
\$\endgroup\$
  • 2
    \$\begingroup\$ Nice. I think there may be an issue though, since arrays are disallowed. Really nice though. \$\endgroup\$ – AJMansfield Jun 22 '14 at 2:03
  • \$\begingroup\$ @AJMansfield One could argue this doesn't have arrays but strings (yes, at low level strings are byte arrays). :) \$\endgroup\$ – seequ Jun 22 '14 at 17:24
  • \$\begingroup\$ @seequ One could also argue that this invalid because of it's use of RAM (yes, at low level, ram is technically an indexed array) ¯_(ツ)_/¯ \$\endgroup\$ – Stan Strum Sep 27 '17 at 20:46
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well done!! Now let's see if someone can get to 4.. \$\endgroup\$ – nbubis Jun 20 '14 at 0:48
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Pinna_be Jun 20 '14 at 20:27
  • \$\begingroup\$ depends how the rules are interpreted, but you have a valid point \$\endgroup\$ – Willem Jun 21 '14 at 4:38
1
\$\begingroup\$

C - 6

(n - (((n * 0xAAAB) >> 19)) * 12 )
\$\endgroup\$
  • \$\begingroup\$ This should either be part of the question or just another answer. I suggest the latter. \$\endgroup\$ – Jwosty Jun 20 '14 at 1:12
  • \$\begingroup\$ @Jwosty - changed. \$\endgroup\$ – nbubis Jun 20 '14 at 23:16
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Runer112 Jun 20 '14 at 2:37
  • \$\begingroup\$ @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. \$\endgroup\$ – Kyle Kanos Jun 20 '14 at 2:42
  • \$\begingroup\$ 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. \$\endgroup\$ – Runer112 Jun 20 '14 at 2:47
  • 1
    \$\begingroup\$ "May use arbitrary number of constant uints." - i.e. cannot use arbitrary floats. \$\endgroup\$ – nbubis Jun 20 '14 at 5:12
  • 1
    \$\begingroup\$ @nbubis: that line does not actually put a restriction on floats. \$\endgroup\$ – Kyle Kanos Jun 20 '14 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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