如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
这是Python中的,基本上,字符串比较和一个状态机。
def divide_by_3(input):
to_do = {}
enque_index = 0
zero_to_9 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
leave_over = 0
for left_over in (0, 1, 2):
for digit in zero_to_9:
# left_over, digit => enque, leave_over
to_do[(left_over, digit)] = (zero_to_9[enque_index], leave_over)
if leave_over == 0:
leave_over = 1
elif leave_over == 1:
leave_over = 2
elif leave_over == 2 and enque_index != 9:
leave_over = 0
enque_index = (1, 2, 3, 4, 5, 6, 7, 8, 9)[enque_index]
answer_q = []
left_over = 0
digits = list(str(input))
if digits[0] == "-":
answer_q.append("-")
digits = digits[1:]
for digit in digits:
enque, left_over = to_do[(left_over, int(digit))]
if enque or len(answer_q):
answer_q.append(enque)
answer = 0
if len(answer_q):
answer = int("".join([str(a) for a in answer_q]))
return answer
其他回答
愚蠢的情况需要愚蠢的解决方案:
#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;
}
如果还需要小数部分,只需将result声明为double,并将fmod(number,除数)的结果添加到它。
解释它是如何工作的
fwrite写入number字节(在上面的例子中number为123456)。 “倒带”将文件指针重置到文件的前面。 Fread从文件中读取长度为除数的最多数量的“记录”,并返回它所读取的元素的数量。
如果你写30个字节,然后以3为单位读回文件,你会得到10个“单位”。30 / 3 = 10
这是我小时候爷爷教我的一个方法。它需要+和/运算符,但计算起来很简单。
把每个数字相加,然后看看它是否是3的倍数。
但这种方法适用于大于12的数字。
例如:36岁,
3+6=9,是3的倍数。
42,
4+2=6,是3的倍数。
(注意:查看下面的编辑2以获得更好的版本!)
这并不像听起来那么棘手,因为你说“没有使用[..+[…]运营商”。如果你想禁止同时使用+字符,请参见下面。
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;
}
然后用div_by(100,3)将100除以3。
编辑:你可以继续并替换++操作符:
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)
}
编辑2:稍快的版本,不使用任何包含+、-、*、/、%字符的操作符。
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;
}
我们使用add函数的第一个参数,因为不使用*字符就不能表示指针的类型,除非在函数形参列表中,其中的语法类型[]与类型* const相同。
FWIW,你可以很容易地实现一个乘法函数使用类似的技巧使用0x55555556技巧提出的AndreyT:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
第一:
x/3 = (x/4) / (1-1/4)
然后求x/(1 - y)
x/(1-1/y)
= x * (1+y) / (1-y^2)
= x * (1+y) * (1+y^2) / (1-y^4)
= ...
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
y = 1/4:
int div3(int x) {
x <<= 6; // need more precise
x += x>>2; // x = x * (1+(1/2)^2)
x += x>>4; // x = x * (1+(1/2)^4)
x += x>>8; // x = x * (1+(1/2)^8)
x += x>>16; // x = x * (1+(1/2)^16)
return (x+1)>>8; // as (1-(1/2)^32) very near 1,
// we plus 1 instead of div (1-(1/2)^32)
}
虽然它使用了+,但有人已经实现了按位操作的add。
好吧,我想我们都同意这不是一个现实世界的问题。为了好玩,这里是如何用Ada和多线程来做这件事:
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;