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.

Quoting this question on SO (Spoiler alert!):

This question has been asked in an Oracle interview.

How would you divide a number by 3 without using *, /, +, -, %, operators?

The number may be signed or unsigned.

The task is solvable, but see if you can write the shortest code.

Rules:

  • Perform the required integer division (/3)
  • Do not use the non-text-based operators *, /, +, -, or % (or their equivalents, such as __div__ or add()). Use of operators for string concatenation and formatting are ok.
  • Input value can be arbitrarily large (whatever your system can handle), both positive and negative
  • Input can be on STDIN or ARGV or entered any other way
  • Create the shortest code you can to do the above
share|improve this question
1  
hopefully by "number" you mean "integer" –  ardnew Aug 1 '12 at 4:06
    
Is it integer division? Also, can we use the characters */+-% in a string? –  beary605 Aug 1 '12 at 5:04
    
Yes, integer. @beary605 Yes, you can use in a string. Updating question for both. –  Gaffi Aug 1 '12 at 5:08
    
This would be much more interesting if you banned any function that internally uses *, /, +, -, or % too - i.e. it would force us to write custom printf() and atoi() calls... :-) –  baby-rabbit Aug 1 '12 at 6:18
1  
@lnkbug, ~0 is just as short... –  Peter Taylor Aug 1 '12 at 17:20

43 Answers 43

up vote 12 down vote accepted

J, 45 44 10 chars

".,&'r3'":

Works with negatives:

".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

": - format as text

,&'r3' - append r3 to the end

". - execute the string, e.g. 15r3

share|improve this answer
1  
It works if you do 3 3 3 #: 9. It looks like you need to know how long your ternary number will be. _3]\i. is also a possible starting point for something, but I don't know if it would be shorter than your solution here. The problem with #_3]\i. as it stands is that it always rounds up instead of down. –  Gareth Aug 17 '12 at 11:21
1  
Maybe ##~3=_3#\i. for 11 characters? –  Gareth Aug 17 '12 at 11:31
1  
Actually, you can shrink yours down to 10 characters with ##~0 0 1$~. –  Gareth Aug 17 '12 at 11:34
1  
You can shrink that down using a hook to 3#.}:(#:~$&3) but it's still longer and it doesn't fix the negative number issue. –  Gareth Aug 17 '12 at 11:54
1  
Yes, you can use either the Power function ^: or Agenda @. for an if or if...else replacement. In this case you might be able to use @. with two verbs connected with a '`' character (a gerund in J-speak) to select one or the other based on a condition. –  Gareth Aug 17 '12 at 13:43

C, 167503724710

Here's my solution to the problem. I admit it is unlikely to win a strict code golf competition, but it doesn't use any tricks to indirectly call built-in division functionality, it is written in portable C (as the original Stack Overflow question asked for), it works perfectly for negative numbers, and the code is exceptionally clear and explicit.

My program is the output of the following script:

#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

Character count: 71 + 39 * 2**32 + 95 = 167503724710

Benchmarks

It was asked how long this would take and how much memory it would use, so here are some benchmarks:

  • Script execution time — Running ./test.py | pv --buffer-size=1M --average-rate > /dev/null for about 30 seconds gives a rate of about 14.8 MB/s. The rate of output can reasonably be assumed to be roughly constant, so the running time to completion should be about 167503724710 B / (14.8 * 1048576 B/s) ≈ 10794 s.
  • Compilation time — The TCC compiler claims to compile C code at 29.6 MB/s, which makes for a compilation time of 167503724710 B / (29.6 * 1048576 B/s) ≈ 5397 s. (Of course this can run in a pipeline with the script.)
  • Size of compiled code — I tried estimating it using ./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null, but it seems tcc doesn't output anything until it reads the entire source file in.
  • Memory usage to run — Since the algorithm is linear (and tcc doesn't optimize across lines), the memory overhead should be only a few kilobytes (apart from the code itself, of course).
share|improve this answer
8  
This is the epitome of hardcoding. ++++++++++ –  Joe Z. Sep 14 '13 at 18:45
1  
That being said, I'm sure if you gave them a 160 GB source file and asked them to compile and test it, they'd look at you like you were crazy. –  Joe Z. Sep 14 '13 at 18:46
2  
If my boss asked me to compute a division by three without - + / * % I would think he's crazy. –  Mikaël Mayer Jan 2 at 12:35
    
And yet, a[b] is a syntactic sugar for *(a + b), which does the addition. –  xfix Jan 2 at 14:17
2  
@NicolasBarbulesco There is a size restriction on Stack Exchange answers. –  Timtech Jan 3 at 23:17

Ruby 33 31

p gets.to_i.to_s(3).chop.to_i 3

To divide by 3 we just need to remove the trailing zero in base 3 number: 120 -> 11110 -> 1111 -> 40

Works with negatives:

ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5

Ruby, 60

Alternatively, w/o using base conversion:

d=->n{x=n.abs;r=(0..1.0/0).step(3).take(x).index x;n>0?r:-r}
share|improve this answer
    
The alternate without base conversion has the banned / operator where Float::INFINITY became 1.0/0. With Ruby 2.1, one may golf (0..1.0/0).step(3) into 0.step(p,3), removing the /. The bigger problem is that -r uses - to negate. It costs 5 characters to change -r to ~r.pred, abusing Integer#pred to subtract 1 without the subtraction operator. –  kernigh May 25 at 15:57

Mathematica, 13 chars

Mean@{#,0,0}&
share|improve this answer
    
This is wicked :D I guess you could save the & and use a plain variable (others here do that too). –  Yves Klett Jan 3 at 10:20

Python, 41 38

print"-"[x:]+`len(xrange(2,abs(x),3))`

xrange seems to be able to handle large numbers (I think the limit is the same as for a long in C) almost instantly.

>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602
share|improve this answer
2  
10/3 equals 3, not 4. –  Joel Cornett Aug 1 '12 at 11:14
    
Thanks; fixed now. –  grc Aug 1 '12 at 12:39
    
Doing print" -"[x<0]+len(range(2,abs(x),3))`` will shave it down to 39 chars –  Joel Cornett Aug 4 '12 at 19:37
    
golfexchange's comment formatting is messing it up. on the above I used backticks to enclose len() as shorthand for repr() –  Joel Cornett Aug 4 '12 at 19:38
2  
Pretend it's Python 3 ;) I like the single char slicing btw. –  Joel Cornett Aug 5 '12 at 1:47

Haskell, 90 106

d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

Creates an infinite (lazy) lookup list [(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...], trims all elements that don't match n (/= is inequality in Haskell) and returns the first which does.

This gets much simpler if there are no negative numbers:

25 27

(([0..]>>=replicate 3)!!)

simply returns the nth element of the list [0,0,0,1,1,1,2, ...].

share|improve this answer
2  
o.O i never thought of that second solution. I might be able to implement something like that in python –  acolyte Aug 2 '12 at 19:19

JavaScript, 56

alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

Makes a string of length n of repeating ,s and replaces ,,, with 1. Then, it measures the string's resulting length. (Hopefully unary - is allowed!)

share|improve this answer
    
+1 for using string ops for division. –  DocMax Aug 26 '12 at 3:32
    
+1 but it doesn't work with negative values –  Francesco Casula Mar 6 at 9:28

C, 160 chars

Character by character long division solution using lookup tables, i.e. without string atoi() or printf() to convert between base 10 strings and integers.

Output will sometimes include a leading zero - part of it's charm.

main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

Note:

  • abuses array access to implement addition.
  • compiles with clang 4.0, other compilers may barf.

Testing:

./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670
share|improve this answer

C 83 characters

The number to divide is passed in through stdin, and it returns it as the exit code from main() (%ERRORLEVEL% in CMD). This code abuses some versions of MinGW in that when optimizations aren't on, it treats the last assignment value as a return statement. It can probably be reduced a bit. Supports all numbers that can fit in to an int

If unary negate (-) is not permitted: (129)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

If unary negate IS permitted: (123)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

EDIT: ugoren pointed out to me that -~ is an increment...

83 Characters if unary negate is permitted :D

main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}
share|improve this answer
    
If unary negate is permitted, x+3 is -~-~-~x. –  ugoren Nov 23 '12 at 9:11
    
Thank you for that. I don't know why that never occurred to me. I guess I didn't realize you could stack unaries so gratuitously hehe. –  Kaslai Nov 24 '12 at 7:59

C, 139 chars

t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

Run with number as command line argument

  • Handles both negative and positive numbers

Testing:

 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

Edits:

  • saved 10 chars by shuffling addition (A) to remove local variables.
share|improve this answer
1  
Nicely done. I tried my best at bit twiddling and got to 239. I just can't get my head around your A, my function just checks the bit i in number n. Does C standard allow omitting type declarations or is that some compiler thing? –  shiona Aug 1 '12 at 9:28
1  
C will assume int if unspecified. –  Wug Aug 3 '12 at 14:48

C# 232

My first code golf... And since there wasn't any C# and I wanted to try a different method not tried here, thought I would give it a shot. Like some others here, only non-negative numbers.

class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}
share|improve this answer

Python 42

int(' -'[x<0]+str(len(range(2,abs(x),3))))

Since every solution posted here that Ive checked truncates decimals here is my solution that does that.

Python 50 51

int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

Since python does floor division, here is my solution that implements that.

Input integer is in the variable x.

Tested in Python 2.7 but I suspect it works in 3 as well.

share|improve this answer
    
+1 For offering both alternatives to the negative value situation. Since there are already so many answers, I'll not be adjusting the spec to exclude one or the other option, though I would personally agree that -3 is the correct answer to -10/3. –  Gaffi Aug 1 '12 at 13:47
    
For those who care about floor division in python: python-history.blogspot.com/2010/08/… –  Matt Aug 1 '12 at 14:22
    
what's with the multiplication and subtraction in your second solution? –  boothby Aug 1 '12 at 15:40
    
@boothby The second solution implements floor division. I wanted to do range(0,abs(x),3) for negative numbers and range(2,abs(x),3) for positive numbers. In order to do that I had range(2... then i subtracted 2 when x is negative. X<0 is True when x is negative, (True)*2 == 2 –  Matt Aug 1 '12 at 16:34
    
I'm not understanding the difference between floor division and truncating decimals. Does this have to with negative division? –  Joel Cornett Aug 1 '12 at 19:12

JavaScript, 55

alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

If one can't use -1, then here is a version replacing it with ~0 (thanks Peter Taylor!).

alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))
share|improve this answer
    
What does ~~ mean in javascript? –  mlatu Aug 2 '12 at 15:55
1  
@ArtemIce One ~ is a Bitwise operator which inverts the bits of the operand (first converting it to a number). This is the shortest way to convert a string to a number (as far as I know). –  Inkbug Aug 3 '12 at 10:02
1  
I feel like using string parsing/conversion is cheating, since its a) a very complicated and expensive process compared to bitwise operations, b) uses the forbidden operators internally, and c) would take up waaaaay more characters than a homerolled solution. Kind of like how people get grumpy when you use the built in sorts when asked to implement a quicksort. –  Wug Aug 3 '12 at 14:46
1  
@Sam Also, ~~ converts to an integer, as opposed to +. –  Inkbug Aug 5 '12 at 4:51
3  
+1 for taking advantage of different bases. It's one of my favorite JavaScript golf techniques. –  DocMax Aug 26 '12 at 3:32

Perl (26 22)

$_=3x pop;say s|333||g

This version (ab)uses Perl's regex engine. It reads a number as the last command line argument (pop) and builds a string of 3s of this length ("3" x $number). The regex substitution operator (s///, here written with different delimitiers because of the puzzle's rules and with a global flag) substitues three characters by the empty string and returns the number of substitutions, which is the input number integer-divided by three. It could even be written without 3, but the above version looks funnier.

$ perl -E '$_=3x pop;say s|333||g' 42
14
share|improve this answer
2  
Hey @memowe, nice work! You could save a few more chars (4) by doing $_=3x pop;say s|333||g. –  Dom Hastings Jan 2 at 10:43
2  
Thanks @DomHastings, I updated the answer! :-) –  memowe Jan 3 at 11:33
1  
When the input is 0, 1, or 2, then it prints an empty string. If it needs to print 0, then it needs 3 more characters (25 total): '$_=3x pop;say s|333||g||0. Slow with large numbers like 99999999, and doesn't work with negative numbers. –  kernigh May 25 at 16:04

ZSH — 31 20/21

echo {2..x..3}|wc -w

For negative numbers:

echo {-2..x..3}|wc -w

With negative numbers (ZSH + bc) — 62 61

I probably shouldn't give two programs as my answer, so here's one that works for any sign of number:

echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

This uses the same base conversion trick as Artem Ice's answer.

share|improve this answer

Ruby (43 22 17)

Not only golf, but elegance also :)

p Rational gets,3

Output will be like (41/1). If it must be integer then we must add .to_i to result, and if we change to_i to to_f then we will can get output for floats also.

share|improve this answer
1  
nice idea.............. –  mlatu Aug 21 '12 at 22:01
1  
Works without the require rational line on Ruby 1.9.3. Omitting the parentheses saves one more char. –  steenslag Dec 3 '12 at 20:53

Python 2.x, 54 53 51

print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))

Where _ is the dividend and is entered as such.

>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

Note: Not sure if using the interactive interpreter is allowed, but according to the OP: "Input can be on STDIN or ARGV or entered any other way"

Edit: Now for python 3 (works in 2.x, but prints a tuple). Works with negatives.

share|improve this answer
    
Works in python 3 as well? –  Mechanical snail Aug 1 '12 at 9:42
    
Doesn't have to be subscriptable; having __len__ is enough. –  Mechanical snail Aug 1 '12 at 10:08
    
len(range(100,1000)) gives 900 in 3.2.3 on linux. –  Mechanical snail Aug 1 '12 at 10:09
    
This doesn't work for negative numbers. And len(xrange(0,_,3)) is shorter and massively faster anyway. –  grc Aug 1 '12 at 10:20
    
@Mechanicalsnail: Point taken. I concede. It does work on 3. –  Joel Cornett Aug 1 '12 at 11:04

C++, 191

With main and includes, its 246, without main and includes, it's only 178. Newlines count as 1 character. Treats all numbers as unsigned. I don't get warnings for having main return an unsigned int so its fair game.

My first ever codegolf submission.

#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

uses shifts to divide number by 4 repeatedly, and calculates sum (which converges to 1/3)

Pseudocode:

// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

As an aside, I could eliminate the main method by naming d main and making it take a char ** and using the programs return value as the output. It will return the number of command line arguments divided by three, rounded down. This brings its length to the advertised 191:

#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}
share|improve this answer

Python2.6 (29)(71)(57)(52)(43)

z=len(range(2,abs(x),3))
print (z,-z)[x<0]

print len(range(2,input(),3))

Edit - Just realized that we have to handle negative integers too. Will fix that later

Edit2 - Fixed

Edit3 - Saved 5 chars by following Joel Cornett's advice

Edit4 - Since input doesn't have to be necessarily be from STDIN or ARGV, saved 9 chars by not taking any input from stdin

share|improve this answer
    
Go ahead with abs() –  mlatu Aug 3 '12 at 7:53
    
shorter to do print z if x==abs(x) else -z –  Joel Cornett Aug 3 '12 at 7:53
    
better yet, print (z,-z)[x<0] –  Joel Cornett Aug 3 '12 at 7:54
    
@ArtemIce thanks, only realized I could use that after reading another answer above. –  elssar Aug 3 '12 at 7:57
    
@JoelCornett humm, didn't know about that, thanks –  elssar Aug 3 '12 at 7:58

Javascript, 47 29

Uses eval to dynamically generate a /. Uses + only for string concatenation, not addition.

alert(eval(prompt()+"\57"+3))

EDIT: Used "\57" instead of String.fromCharCode(47)

share|improve this answer

Golfscript - 13 chars

~3base);3base
share|improve this answer
    
doesn't seem to handle negative input –  r.e.s. Aug 19 '12 at 18:05
1  
@r.e.s. s/seem to // :(. I'll have to have a think about it –  gnibbler Aug 19 '12 at 22:30

C, 81 73 chars

Supports non-negative numbers only.

char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

The idea is to use pointer arithemtic. The number is read into the pointer x, which doesn't point anywhere. &x[~2] = &x[-3] = x-3 is used to subtract 3. This is repeated as long as the number is above 2. i counts the number of times this is done (&i[1] = i+1).

share|improve this answer
    
+1: very clever use of pointer arithmetic –  Paul R Aug 2 '12 at 21:16
    
Trying to understand the code,somebody shed some lights? Thanks –  Cong Hui Oct 21 '13 at 19:15
    
@Chui, added explanation. –  ugoren Oct 22 '13 at 11:07
    
@ugoren as far as I understand, shouldn't printf("%d") print out the memory address pointer i holds in Hex? why it is printing out an integer? or char* i was initialized to point to memory address 0 by default? Thanks –  Cong Hui Oct 22 '13 at 21:23

Java

Assume the integer is in y:

Converts to a string in base 3, removes the last character ( right shift ">>" in base 3 ), then converts back to integer.

Works for negative numbers.

If the number, y, is < 3 or > -3, then it gives 0. ( ~2 = -3 )

System.out.print(~2<y&&y<3?0:Integer.valueOf(Integer.toString(y,3).split(".$")[0],3));

First time posting on code golf. =) So can't comment yet.

share|improve this answer

Clojure, 87; works with negatives; based on lazyseqs

(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

Ungolfed:

(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))
share|improve this answer

Sage Notebook (21)

ZZ(n.digits(3)[1:],3)
share|improve this answer

Mathematica 36 51 42 chars

This is easily achieved in base 3.

IntegerDigits[n,3] converts the absolute value of the number to base 3.

Most takes all but the rightmost digit. This "rightward shift" amounts to integer division by 3.

FromDigits converts back to base 10.

Sign restores, if necessary, the sign.

Sign@n*Most@IntegerDigits[n,3]~FromDigits~3
share|improve this answer

F# (81)

Using inclusive ranges:

let(^)s x=if s<0 then int("-"+string x)else x
let d m =sign m^[3..3..abs m].Length

Alternatively, using strings:

let (^) s x = if s < 0 then int("-" + string x) else x
let d m =
  let n = abs m
  [0..n]
  |> Seq.map (fun i -> i, String.replicate i "aaa")
  |> Seq.takeWhile (fun (i, s) -> s.Length <= n)
  |> Seq.last
  |> fst
  |> (^) (sign m)

This is verbose but it's better than being forced to use loops in many imperative languages. String.replicate is especially valuable.

share|improve this answer
    
This looks like it uses multiplication * to restore the sign bit. –  kernigh May 25 at 16:25

PowerShell 57 or 46

In 57 characters using % as the PowerShell foreach operator, not modulo. This solution can accept positive or negative integers.

(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

In 46 characters if * is allowed as the string repetition operator, not multiply. This option requires positive integers as input values.

("1"*(Read-Host)-replace111,0-replace1).Length
share|improve this answer

Scala 96

def d(x:Int)={val y=x.abs;val r=0.to(y).flatMap(List.fill(3)(_)).drop(y).head;if(x==y)r else -r}

I do realize now it is basically the same idea behind some other answers here (Haskell, Clojure and the 2nd take of this one in Ruby, to name a few)... :-/

share|improve this answer

C++ 633 byes (including whitespace; 457 bytes excluding scaffolding)

I know this is not anywhere near the shortest code, but it does have some "advantages". First the code:

#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;typedef int I;typedef unsigned U;U A(U l,U r){U t;while(r)t=l^r,r=(l&r)<<1,l=t;return l;}
#define N(l)A(~l,1)
#define S(l,r)A(l,N(r))
U M(U l, U r){U p=0;while(r){if(r&1)p=A(p,l);l<<=1;r>>=1;}return p;}U D(U n,U&r){U m=U(1)<<S(M(sizeof(U),CHAR_BIT),1),q=r=0,x=1;while(x){q<<=1;r<<=1;if(n&m)r|=1;if(r>=3)q|=1,r=S(r,3);n<<=1;x<<=1;}return q;}I D(I n,I&r){bool o=n<0;U p=o?N(n):n,s,t;s=D(p,t);r=o?N(t):t;return o?N(s):s;}I main(I c,char**v){I i=1,q,r;while(i<c)q=D(atoi(v[i]),r),cout<<v[i]<<" divided by 3 == "<<q<<" with a remainder of "<<r<<endl,i=A(i,1);}

The advantages over the other solutions, even though it can't win on a purely codegolf basis:

  • It only uses the standard library to obtain the value of CHAR_BIT, atoi, cout, and endl. Consequently, it does not depend on any math routines in the standard library beyond those to convert a string to and from a number. It most definitely does not use any part of the standard library to divide by 3.
  • It at no time uses any of the operators + - * / % (binary or unary, numeric or string). Note that it does use two asterisks to declare a pointer to a pointer to char, but it only uses that to access command line parameters of number to divide.
  • It uses bit manipulation and relational operators exclusively in the division process.
  • If the scaffolding code (main and two of the three include files) is removed, the code that does the actual work of division by 3 is only 457 bytes.
  • I'm pretty sure this code should work on any C++ compiler conforming to the standard and does not exploit any tricks that only work on a subset of compilers or platforms. One possible exception to this is it might not work on a platform that does not use twos complement signed integers, though I don't have access to any platform like that to test that theory. Another possible exception (related) is if automatic signed / unsigned conversions are not supported as they are for most (or all) platforms utilizing twos complement signed integers.

I'm sure there are other ways to make this shorter, but I've spent enough time on it. Mainly I wanted to perform the exercise without any "cheating" via use of any operations from the standard library. By defining functions and macros that perform unary negation, addition, subtraction, multiplication, and division strictly in terms of bit level operations and relational operators, signed (or unsigned) integers can be divided by three. I've hard coded the divisor to 3 to remove a few bytes of code here and there, though adding a parameter to pass in the divisor is fairly trivial.

The signed division function notes the sign of the dividend then calls the unsigned division function with the dividends absolute value. Once the unsigned division returns the unsigned quotient and remainder, the original sign is used to negate the signed quotient and remainder as needed.

Edit: Only after I wrote and submitted my solution did I go look at the original question on SO. Some interesting stuff there, and of course someone had already come up with my solution. FWIW, I did write this on my own! Not that it matters for this old of a question, especially in a codegolf exercise. :)

share|improve this answer

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.