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.

• qwr: @GregHewgill My typo, it should be 8 bit number.
• Jwosty: Are we only allowed to use the above operators? Otherwise, modulo would make this way too easy.
• Greg Hewgill: Also, how about table lookup?
• Ruslan: 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?
• qwr: @Ruslan You are only allowed to use the above.

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.

• n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳: +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.
• aditsu quit because SE is EVIL: @DigitalTrauma inequality operators are allowed, not banned
• Digital Trauma: @aditsu Oops! I need to read more carefully sometimes! +1 great answer!
• Kartik_Koro: @aditsu, sorry I'm noob, how exactly does this work?
• aditsu quit because SE is EVIL: @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

Answer 2

Python, (削除) 3 (削除ここまで) 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

• qwr: Wow! Your solution is probably the shortest (3 tokens), but I want to encourage other answers too.
• Howard: There is even a 2 token solution: 0x9......>>x&1.

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

• qwr: 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
• aditsu quit because SE is EVIL: 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
• aditsu quit because SE is EVIL: Rats, even 43 = (2^7 + 1)/3 works, not sure how I missed it. Edited now.

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.

• Paul R: +1: interestingly this works for n up to 512 (actually n = 590), but I'm not quite sure why.
• n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳: @PaulR: It won't work for bigger numbers due to carry (note that I used addition in the calculation). Also note the repeated lines.
• Paul R: Yes, I'm just not sure why it works for 9 bit values, since it only seems to be testing 8 bits?
• phuclv: 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
• phuclv: 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

Answer 5

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x

• aditsu quit because SE is EVIL: Duplicate of Howard's comment
• ɐɔıʇǝɥʇuʎs: @aditsu ... Great minds think alike? I swear I didn't see that before I posted this.

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.

• n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳: Should be 4 tokens: =, *, |, ==
• Tyilo: I don't think variable assignment counts as a token.

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

• C5H8NNaO4: Wouldn't a token in the OP's sense be only one of the above listed in the question?
• Not that Charles: @C5H8NNaO4 So what? 0?
• Not that Charles: @C5H8NNaO4 maybe 4 for constants?
• Kai Burghardt: @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.

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

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;

Answer 12

Tcl, 80 bytes

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

Try it online!

• sergiol: 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!
• sergiol: Another fail:**87 bytes** proc T n {expr {[expr [join [split [expr [join [split $n ""] +]] ""] +]] in {0 3 6 9}}} Try it online!
• qwr: This is an ancient question of mine tagged atomic-code-golf. That means the scoring is in predefined tokens, not bytes.
• sergiol: I don't know how to account tokens @qwr