如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
以下是我的解决方案:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
首先,请注意
1/3 = 1/4 + 1/16 + 1/64 + ...
现在,剩下的很简单!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
现在我们要做的就是把a的这些位移位值加在一起!哦!但是我们不能做加法,所以我们必须使用位操作符来编写一个加法函数!如果您熟悉逐位操作符,那么我的解决方案应该看起来相当简单……但以防你不懂,我会在最后讲一个例子。
另一件需要注意的事情是,首先我左移30!这是为了确保分数不会四舍五入。
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
这就是你小时候学过的简单加法!
111
1011
+0110
-----
10001
这个实现失败了,因为我们不能把方程的所有项相加:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
假设div_by_3(a) = x的结果,则x <= floor(f(a, i)) < a / 3。当a = 3k时,我们得到错误的答案。
其他回答
下面的脚本生成了一个C程序,可以在不使用运算符* / + - %的情况下解决这个问题:
#!/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));
}
''')
使用itoa转换为以3为基数的字符串。去掉最后一个小调,转换回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) // Remove sign if positive
str[0] = ' ';
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
}
这是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
这个方法(c#)怎么样?
private int dividedBy3(int n) {
List<Object> a = new Object[n].ToList();
List<Object> b = new List<object>();
while (a.Count > 2) {
a.RemoveRange(0, 3);
b.Add(new Object());
}
return b.Count;
}
首先是我想到的。
irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub(' ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222
编辑:对不起,我没有注意到标签c。但是你可以使用字符串格式的想法,我猜…