Divide a number by 3 without using *, /, +, -, % operators

妖狐艹你老母 2022-05-24 05:56 140阅读 0赞

原帖: [http://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators][http_stackoverflow.com_questions_11694546_divide-a-number-by-3-without-using-operators]

===============================================================================================================================

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.

===============================================================================================================================

There is a simple function I found [here][]. but it's using the + operator, so you have to add the values with the bit-operators:

// replaces the + operator int add(int x, int y) {     int a, b;     do {         a = x & y;         b = x ^ y;         x = a << 1;         y = b;     } while (a);     return b; } int divideby3 (int num) {     int sum = 0;     while (num > 3) {         sum = add(num >> 2, sum);         num = add(num >> 2, num & 3);     }     if (num == 3)         sum = add(sum, 1);     return sum; }

As Jim commented this works because:

*  `n = 4 * a + b`
 *  `n / 3 = a + (a + b) / 3`
 *  So `sum += a`, `n = a + b`, and iterate.
 *  When `a == 0 (n < 4)`, `sum += floor(n / 3)`; i.e. `1`, `if n == 3, else 0`

===============================================================================================================================

Idiotic conditions call for an idiotic solution:

#include <stdio.h> #include <stdlib.h> int main() {     FILE * fp=fopen("temp.dat","w+b");     int number=12346;     int divisor=3;     char * buf = calloc(number,1);     fwrite(buf,number,1,fp);     rewind(fp);     int result=fread(buf,divisor,number,fp);     printf("%d / %d = %d", number, divisor, result);     free(buf);     fclose(fp);     return 0; }

If also the decimal part is needed, just declare `result` as `double` and add to it the result of`fmod(number,divisor)`.

Explanation of how it works

1.  The `fwrite` writes `number` bytes (number being 123456 in the example above).
2.  `rewind` resets the file pointer to the front of the file.
3.  `fread` reads a maximum of `number` "records" that are `divisor` in length from the file, and returns the number of elements it read.

If you write 30 bytes then read back the file in units of 3, you get 10 "units". 30 / 3 = 10

===============================================================================================================================

log(pow(exp(number),0.33333333333333333333)) /* :-) */

===============================================================================================================================

Using cloud computing :D

[Google Search: `30 divided by 3`][Google Search_30 divided by 3]

// 这个太威武了! 哈哈......

===============================================================================================================================

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) {     int num = 1234567;     int den = 3;     div_t r = div(num,den); // div() is a standard C function.     printf("%d\n", r.quot);     return 0; }

===============================================================================================================================

Use inline assembler: [(also works for negative numbers now)][also works for negative numbers now]

#include <stdio.h> int main() {   int dividend = -42, divisor = 3, quotient, remainder;   __asm__ ( "movl   %2, %%edx;"             "sarl  $31, %%edx;"             "movl   %2, %%eax;"             "movl   %3, %%ebx;"             "idivl      %%ebx;"           : "=a" (quotient), "=d" (remainder)           : "g"  (dividend), "g"  (divisor)           : "ebx" );   printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder); }

===============================================================================================================================

Use itoa to convert to base 3 string. Drop last trit and convert back to base 10.

// Note: itoa is non-standard but actual implementations // don't seem to handle negative when base != 10 int div3(int i) {   char str[42];   sprintf(str, "%d", INT_MIN); // put minus sign at str[0]   if (i>0) str[0] = ' ';       // remove sign if positive   itoa(abs(i), &str[1], 3);    // put ternary absolute value starting at str[1]   str[strlen(&str[1])] = '\0'; // drop last digit   return strtol(str, NULL, 3); // read back result }

===============================================================================================================================

The request says "a number", not "any number", so:

1.  Check if the number is 3.
2.  If so, return 1.
3.  If not, report an invalid input.

Job done, but for extra marks, you could implement a dictionary of commonly requested multiples of three.

===============================================================================================================================

(note: see Edit 2 below for a better version!)

This is not as tricky as it sounds, because you said "without using the \[..\] `+` \[..\] operators". See below, if you want to forbid using the `+` character all together.

unsigned div_by(unsigned const x, unsigned const by) {   unsigned floor = 0;   for (unsigned cmp = 0, r = 0; cmp <= x;) {     for (unsigned i = 0; i < by; i++)       cmp++; // that's not the + operator!     floor = r;     r++; // neither is this.   }   return floor; }

then just say `div_by(100,3)` to divide `100` by `3`.

--------------------

### Edit: You can go on and replace the `++` operator as well: ###

unsigned inc(unsigned x) {   for (unsigned mask = 1; mask; mask <<= 1) {     if (mask & x)       x &= ~mask;     else       return x & mask;   }   return 0; // overflow (note that both x and mask are 0 here) }

--------------------

# Edit 2: Slightly faster version without using any operator that contains the `+`,`-`,`*`,`/`,`%` characters. #

unsigned add(char const zero[], unsigned const x, unsigned const y) {   // this exploits that &foo[bar] == foo+bar if foo is of type char*   return (int)(uintptr_t)(&((&zero[x])[y])); } unsigned div_by(unsigned const x, unsigned const by) {   unsigned floor = 0;   for (unsigned cmp = 0, r = 0; cmp <= x;) {     cmp = add(0,cmp,by);     floor = r;     r = add(0,r,1);   }   return floor; }

We use the first argument of the `add` function because we cannot denote the type of pointers without using the`*` character, except in function parameter lists, where the syntax `type[]` is identical to `type* const`.

FWIW, you can easily implement a multiplication function using a similar trick to use the `0x55555556` trick proposed by [AndreyT][]:

int mul(int const x, int const y) {   return sizeof(struct {     char const ignore[y];   }[x]); }

===============================================================================================================================

[http_stackoverflow.com_questions_11694546_divide-a-number-by-3-without-using-operators]: http://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators
[here]: http://www.forums.hscripts.com/viewtopic.php?f=13&t=1358
[Google Search_30 divided by 3]: https://www.google.com/webhp?q=30%20divided%20by%203&oq=30%20divided%20by%203
[also works for negative numbers now]: http://ideone.com/HU3n0
[AndreyT]: http://stackoverflow.com/a/11694787/430766