Determine if an integer is divisible by 3

Question

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.

Answer 1

C - 2 tokens

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

Seems to work up to 2³¹-1.

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

Answer 2

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

Answer 3

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 2³² 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

• Labor of Division - ridiculousfish.com
• Hacker's Delight - Magic Number
• Wikipedia - Modular multiplicative inverse

Answer 4

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 4ⁿ ≡ 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.

Answer 5

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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 ||.

Answer 11

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!

Answer 12

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;