如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
要将一个32位数字除以3,可以将其乘以0x55555556,然后取64位结果的前32位。
现在剩下要做的就是使用位运算和移位来实现乘法…
其他回答
Yet another solution. This should handle all ints (including negative ints) except the min value of an int, which would need to be handled as a hard coded exception. This basically does division by subtraction but only using bit operators (shifts, xor, & and complement). For faster speed, it subtracts 3 * (decreasing powers of 2). In c#, it executes around 444 of these DivideBy3 calls per millisecond (2.2 seconds for 1,000,000 divides), so not horrendously slow, but no where near as fast as a simple x/3. By comparison, Coodey's nice solution is about 5 times faster than this one.
public static int DivideBy3(int a) {
bool negative = a < 0;
if (negative) a = Negate(a);
int result;
int sub = 3 << 29;
int threes = 1 << 29;
result = 0;
while (threes > 0) {
if (a >= sub) {
a = Add(a, Negate(sub));
result = Add(result, threes);
}
sub >>= 1;
threes >>= 1;
}
if (negative) result = Negate(result);
return result;
}
public static int Negate(int a) {
return Add(~a, 1);
}
public static int Add(int a, int b) {
int x = 0;
x = a ^ b;
while ((a & b) != 0) {
b = (a & b) << 1;
a = x;
x = a ^ b;
}
return x;
}
这是c#,因为这是我手边的东西,但与c的区别应该很小。
愚蠢的情况需要愚蠢的解决方案:
#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的数一样多。然后继续将每个未配对的顶点与其他两个顶点配对。
粗糙的伪代码:
function divide(int num)
while(num!=0)
Add a new vertice to vertiexList.
num--
quotient = 0
for each in vertexList(lets call this vertex A)
if vertexList not empty
Add an edge between A and another vertex(say B)
else
your Remainder is 1 and Quotient is quotient
if vertexList not empty
Add an edge between A and another vertex(say C)
else
your remainder is 2 and Quotient is quotient
quotient++
remove A, B, C from vertexList
Remainder is 0 and Quotient is quotient
这显然是可以优化的,复杂度取决于你的数字有多大,但它应该工作,只要你能做++和——。 这就像数更酷的东西一样。
3以2为底等于11。
所以只要做长除法(就像中学那样),以2 × 11为底。以2为底比以10为底更简单。
对于从最有效位开始的每个位位:
判断prefix是否小于11。
如果它是输出0。
如果不是输出1,则替换前缀位进行适当的更改。只有三种情况:
11xxx -> xxx (ie 3 - 3 = 0)
100xxx -> 1xxx (ie 4 - 3 = 1)
101xxx -> 10xxx (ie 5 - 3 = 2)
所有其他前缀都不可达。
重复到最低位,你就完成了。
这是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