20
\$\begingroup\$

Your goal is to determine if a number is divisible by 3 without using conditionals. The input will be an unsigned 8 bit number from 0 to 255. Creativity encouraged!

You are ONLY allowed to use

  • Equality/Inequality (==, !=, >, <, >=, <=)

  • Arithmetic (+, -, x)

  • Logical Operators (! not, && and, || or)

  • Bitwise Operators (~ not, & and, | or, ^ xor, <<, >>, >>> arithmetic and logical left and right shifts)

  • Constants (it would be better if you kept these small)

  • Variable assignment

Output 0 if false, 1 if true.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. Example methods here. A token is any of the above excluding constants and variables.

\$\endgroup\$
10
  • \$\begingroup\$ @GregHewgill My typo, it should be 8 bit number. \$\endgroup\$
    – qwr
    Jun 23, 2014 at 3:33
  • 2
    \$\begingroup\$ Are we only allowed to use the above operators? Otherwise, modulo would make this way too easy. \$\endgroup\$
    – Jwosty
    Jun 23, 2014 at 3:40
  • \$\begingroup\$ Also, how about table lookup? \$\endgroup\$ Jun 23, 2014 at 3:42
  • 4
    \$\begingroup\$ Can you clarify what you mean by no conditionals? Is it limited to IF statements, or does it apply to things like loops as well? \$\endgroup\$
    – Ruslan
    Jun 23, 2014 at 3:50
  • 1
    \$\begingroup\$ @Ruslan You are only allowed to use the above. \$\endgroup\$
    – qwr
    Jun 23, 2014 at 3:54

12 Answers 12

31
\$\begingroup\$

C - 2 tokens

int div3(int x) {
    return x * 0xAAAAAAAB <= x;
}

Seems to work up to 231-1.

Credits to zalgo("nhahtdh") for the multiplicative inverse idea.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ +1. Was baffled a bit at how the <= works, and remembered that 0xAAAAAAAB is taken to be unsigned int type, thus the result of multiplication is unsigned. \$\endgroup\$ Jun 23, 2014 at 7:56
  • \$\begingroup\$ @DigitalTrauma inequality operators are allowed, not banned \$\endgroup\$ Jun 23, 2014 at 17:59
  • \$\begingroup\$ @aditsu Oops! I need to read more carefully sometimes! +1 great answer! \$\endgroup\$ Jun 23, 2014 at 18:01
  • \$\begingroup\$ @aditsu, sorry I'm noob, how exactly does this work? \$\endgroup\$ Jun 24, 2014 at 5:22
  • 2
    \$\begingroup\$ @Kartik_Koro 0xAAAAAAAB * 3 == 1 due to overflow, so for any int x, x * 0xAAAAAAAB * 3 == x. Also y * 3 has different values for different y, therefore y = x * 0xAAAAAAAB must be the only y such that y * 3 == x. If x is a multiple of 3, then y must be x/3, otherwise it must be working through overflow. A simple way to check is to compare y with x. Also see en.wikipedia.org/wiki/Modular_multiplicative_inverse \$\endgroup\$ Jun 24, 2014 at 5:56
17
\$\begingroup\$

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Wow! Your solution is probably the shortest (3 tokens), but I want to encourage other answers too. \$\endgroup\$
    – qwr
    Jun 23, 2014 at 4:05
  • 12
    \$\begingroup\$ There is even a 2 token solution: 0x9......>>x&1. \$\endgroup\$
    – Howard
    Jun 23, 2014 at 5:00
7
\$\begingroup\$

C - 5 4 (?) tokens

int div3_m2(uint32_t n) {
    return n == 3 * (n * 0xAAAAAAABull >> 33);
}

Works for any unsigned 32-bit number.

This code makes use of multiplicative inverse modulo 232 of a divisor to convert division operation into multiplication operation.

Edit

My solution (posted 2 minutes after) has the same spirit as aditsu's solution. Credit to him for the use of == that improves my solution by 1 token.

Reference

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This is incredible. I knew about magic numbers from the famous inverse squareroot trick, but I didn't know it could be used for an arbitrary divisor. This is Bull :P \$\endgroup\$
    – qwr
    Jun 23, 2014 at 7:05
  • \$\begingroup\$ Yep, 0xAAAAAAAB = (2^33 + 1)/3 and 171 = (2^9 + 1)/3. I picked the smallest constant that does the trick. Hmm, actually it also seems to work with 86 = (2^8 + 2)/3 \$\endgroup\$ Jun 23, 2014 at 7:11
  • \$\begingroup\$ Rats, even 43 = (2^7 + 1)/3 works, not sure how I missed it. Edited now. \$\endgroup\$ Jun 23, 2014 at 7:16
4
\$\begingroup\$

C - 15 (?) tokens

int div3_m1(unsigned int n) {
    n = (n & 0xf) + (n >> 4);
    n = (n & 0x3) + (n >> 2);
    n = (n & 0x3) + (n >> 2);
    return n == 0 || n == 3;
}

Since 4 ≡ 1 (mod 3), we have 4n ≡ 1 (mod 3). The digit summing rule is not limited to summing the digits, but also allows us to arbitrarily break the number into sequences of digits and sum all of them up while maintaining the congruency.

An example in base 10, divisor = 9:

1234 ≡ 12 + 34 ≡ 1 + 2 + 3 + 4 ≡ 123 + 4 ≡ 1 (mod 9)

All statements in the program makes use of this property. It can actually be simplified to a loop that runs the statement n = (n & 0x3) + (n >> 2); until n < 4, since the statement simply breaks the number in base-4 at the least significant digit and add the 2 parts up.

\$\endgroup\$
5
  • \$\begingroup\$ +1: interestingly this works for n up to 512 (actually n = 590), but I'm not quite sure why. \$\endgroup\$
    – Paul R
    Jun 23, 2014 at 6:01
  • \$\begingroup\$ @PaulR: It won't work for bigger numbers due to carry (note that I used addition in the calculation). Also note the repeated lines. \$\endgroup\$ Jun 23, 2014 at 6:06
  • \$\begingroup\$ Yes, I'm just not sure why it works for 9 bit values, since it only seems to be testing 8 bits? \$\endgroup\$
    – Paul R
    Jun 23, 2014 at 6:16
  • \$\begingroup\$ for 9-bit numbers after the first addition it become at most 5 bits, after the first n = (n & 0x3) + (n >> 2); the result is reduced to 3 bits and the repetition caused it to remain only 2 bits stackoverflow.com/a/3421654/995714 \$\endgroup\$
    – phuclv
    Jun 23, 2014 at 6:50
  • 1
    \$\begingroup\$ oh I've made a mistake. A 5-bit number + a 4-bit number can result in a 6-bit number. But if n <= 588 adding the top 4 bits and bottom 2 bits of that 6-bit number produce an only 4-bit sum. Again adding that results in a 2-bit number. 589 and 590 results in 3 bits in the last sum but incidentally they aren't divisible by 3 so the result is correct \$\endgroup\$
    – phuclv
    Jun 23, 2014 at 7:09
2
\$\begingroup\$

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Duplicate of Howard's comment \$\endgroup\$ Jun 23, 2014 at 8:31
  • \$\begingroup\$ @aditsu ... Great minds think alike? I swear I didn't see that before I posted this. \$\endgroup\$ Jun 23, 2014 at 8:32
2
\$\begingroup\$

JavaScript - 3 tokens

function div3(n) {
    var a = n * 0.3333333333333333;
    return (a | 0) == a;
}

This abuses the fact that using bitwise operators on a number truncates it to an integer in JavaScript.

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

C - 4 tokens

int div3(int x) {
    return ((x * 43) >> 7) * 3 == x;
}

Works up to 383.

Previous version (bigger constants):

int div3(int x) {
    return ((x * 171) >> 9) * 3 == x;
}

Works up to 1535

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

Befunge 93 - 5 tokens

Fixed - division removed.

v      @._1.@
         \   
         0   
         +   
         3   
>&>3-:0\`|   
  ^      <   

Gets input, keeps subtracting 3 until it's smaller than 0, direct the pointer up ('|'), then adds 3. If the value is 0 then the pointer moves right ("1.@" outputs '1') else moves left ("@." outputs '0'). '@' terminates the program.

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

Ruby, 6(?) tokens

I'm really not sure how to count tokens. OP, can you score me?

I think it's 6... 1, 0, 0, *, 255, x

Note that the * is not integer multiplication.

def div3(x)
  ([1,0,0]*255)[x]
end
\$\endgroup\$
4
  • \$\begingroup\$ Wouldn't a token in the OP's sense be only one of the above listed in the question? \$\endgroup\$
    – C5H8NNaO4
    Jun 23, 2014 at 22:25
  • \$\begingroup\$ @C5H8NNaO4 So what? 0? \$\endgroup\$ Jun 24, 2014 at 2:28
  • \$\begingroup\$ @C5H8NNaO4 maybe 4 for constants? \$\endgroup\$ Jun 24, 2014 at 3:15
  • \$\begingroup\$ @NotthatCharles No, one. A token is any of the above excluding constants and variables. So constants are “non-tokens” (for the purposes of scoring), but the asterisk is a token still. \$\endgroup\$ Sep 4, 2023 at 22:30
0
\$\begingroup\$

Python - 25 tokens

To get things started, I have a lengthy solution that is a implementation of one of the answers in the link in my first post. n is input.

a = (n>>7)-((n&64)>>6)+((n&32)>>5)-((n&16)>>4)+((n&8)>>3)-((n&4)>>2)+((n&2)>>1)-(n&1)
print(a==0 or a==3)

or is equivalent to ||.

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

Tcl, 83 bytes

proc T n {while \$n>9 {set n [expr [join [split $n ""] +]]};expr {$n in {0 3 6 9}}}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Failed outgolf: 96 bytes proc T n {set n [expr [join [split [expr [join [split $n ""] +]] ""] +]];expr {$n in {0 3 6 9}}} Try it online! \$\endgroup\$
    – sergiol
    Apr 10, 2018 at 14:38
  • \$\begingroup\$ Another fail:**87 bytes** proc T n {expr {[expr [join [split [expr [join [split $n ""] +]] ""] +]] in {0 3 6 9}}} Try it online! \$\endgroup\$
    – sergiol
    Apr 10, 2018 at 14:59
0
\$\begingroup\$

Pascal, 1 token

Pascal does not have bitwise operators. (Some dialects do and some implementations use under the hood bitwise operators for operations on the set data type nevertheless.) Since the in set membership operator is not listed among the allowed operators, another relational operator is used:

    type
        wholeNumberLessThan256 = 0..255;
    
    function divisibleByThree(n: wholeNumberLessThan256): Boolean;
        const
            wholeNumbersLessThan256divisibleByThree = [
                      0,   3,   6,   9,  12,  15,  18,  21,  24,  27,
                     30,  33,  36,  39,  42,  45,  48,  51,  54,  57,
                     60,  63,  66,  69,  72,  75,  78,  81,  84,  87,
                     90,  93,  96,  99, 102, 105, 108, 111, 114, 117,
                    120, 123, 126, 129, 132, 135, 138, 141, 144, 147,
                    150, 153, 156, 159, 162, 165, 168, 171, 174, 177,
                    180, 183, 186, 189, 192, 195, 198, 201, 204, 207,
                    210, 213, 216, 219, 222, 225, 228, 231, 234, 237,
                    240, 243, 246, 249, 252, 255];
        begin
            { In Pascal `<=` denotes the `⊆` operator with sets. }
            divisibleByThree := [n] <= wholeNumbersLessThan256divisibleByThree;
        end;

Extended Pascal, 0 token

NB: A lookup table could be written in Standard Pascal (ISO standard 7185), too.

    type
        wholeNumberLessThan256 = 0‥255;
    
    { The reserved word `protected` is defined by Extended Pascal.
      It just means the value of `n` may not be altered in the definition. }
    function divisibleByThree(protected n: wholeNumberLessThan256): Boolean;
        type
            tableFormat = array[type of n] of Boolean;
        const
            lookupTable = tableFormat[
                      0,   3,   6,   9,  12,  15,  18,  21,  24,  27,
                     30,  33,  36,  39,  42,  45,  48,  51,  54,  57,
                     60,  63,  66,  69,  72,  75,  78,  81,  84,  87,
                     90,  93,  96,  99, 102, 105, 108, 111, 114, 117,
                    120, 123, 126, 129, 132, 135, 138, 141, 144, 147,
                    150, 153, 156, 159, 162, 165, 168, 171, 174, 177,
                    180, 183, 186, 189, 192, 195, 198, 201, 204, 207,
                    210, 213, 216, 219, 222, 225, 228, 231, 234, 237,
                    240, 243, 246, 249, 252, 255: true;
                    otherwise false
                ];
        begin
            divisibleByThree ≔ lookupTable[n];
        end;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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