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

2019-01-03 03:56发布

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

The number may be signed or unsigned.

30条回答
我命由我不由天
2楼-- · 2019-01-03 04:17

The following script generates a C program that solves the problem without using the operators * / + - %:

#!/usr/bin/env python3

print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')

for i in range(-2**31, 2**31):
    print('    if(input == %d) return %d;' % (i, i / 3))


print(r'''
    return 42; // impossible
}
int main()
{
    const int32_t number = 8;
    printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')
查看更多
姐就是有狂的资本
3楼-- · 2019-01-03 04:17

Solution using fma() library function, works for any positive number:

#include <stdio.h>
#include <math.h>

int main()
{
    int number = 8;//Any +ve no.
    int temp = 3, result = 0;
    while(temp <= number){
        temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
        result = fma(result, 1, 1);
    } 
    printf("\n\n%d divided by 3 = %d\n", number, result);
}

See my another answer.

查看更多
何必那么认真
4楼-- · 2019-01-03 04:18
log(pow(exp(number),0.33333333333333333333)) /* :-) */
查看更多
萌系小妹纸
5楼-- · 2019-01-03 04:19

Would it be cheating to use the / operator "behind the scenes" by using eval and string concatenation?

For example, in Javacript, you can do

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}
查看更多
劫难
6楼-- · 2019-01-03 04:20

Okay I think we all agree that this isn't a real world problem. So just for fun, here's how to do it with Ada and multithreading:

with Ada.Text_IO;

procedure Divide_By_3 is

   protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;

   protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;

   task type Input is
   end Input;
   task type Output is
   end Output;

   protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;

   protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;

   Collector : Collector_Type;
   Divisor : Divisor_Type;

   task body Input is
   begin
      Divisor.Poke;
   end Input;

   task body Output is
   begin
      Collector.Poke;
   end Output;

   Cur_Input : access Input;

   -- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;
查看更多
Deceive 欺骗
7楼-- · 2019-01-03 04:21

Using Hacker's Delight Magic number calculator

int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}

Where fma is a standard library function defined in math.h header.

查看更多
登录 后发表回答