如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
如何将一个数除3而不使用*、/、+、-、%等运算符?
号码可以有签名,也可以没有签名。
当前回答
在PHP中使用BC数学:
<?php
$a = 12345;
$b = bcdiv($a, 3);
?>
MySQL(来自Oracle的采访)
> SELECT 12345 DIV 3;
帕斯卡:
a:= 12345;
b:= a div 3;
X86-64汇编语言:
mov r8, 3
xor rdx, rdx
mov rax, 12345
idiv r8
其他回答
很有趣的是,没有人回答一个泛泛的划分:
/* For the given integer find the position of MSB */
int find_msb_loc(unsigned int n)
{
if (n == 0)
return 0;
int loc = sizeof(n) * 8 - 1;
while (!(n & (1 << loc)))
loc--;
return loc;
}
/* Assume both a and b to be positive, return a/b */
int divide_bitwise(const unsigned int a, const unsigned int b)
{
int int_size = sizeof(unsigned int) * 8;
int b_msb_loc = find_msb_loc(b);
int d = 0; // dividend
int r = 0; // reminder
int t_a = a;
int t_a_msb_loc = find_msb_loc(t_a);
int t_b = b << (t_a_msb_loc - b_msb_loc);
int i;
for(i = t_a_msb_loc; i >= b_msb_loc; i--) {
if (t_a > t_b) {
d = (d << 1) | 0x1;
t_a -= t_b; // Not a bitwise operatiion
t_b = t_b >> 1;
}
else if (t_a == t_b) {
d = (d << 1) | 0x1;
t_a = 0;
}
else { // t_a < t_b
d = d << 1;
t_b = t_b >> 1;
}
}
r = t_a;
printf("==> %d %d\n", d, r);
return d;
}
按位加法已经在其中一个答案中给出,所以跳过它。
#!/bin/ruby
def div_by_3(i)
i.div 3 # always return int http://www.ruby-doc.org/core-1.9.3/Numeric.html#method-i-div
end
没有反复检查这个答案是否已经发表。如果程序需要扩展到浮点数,可以将这些数字乘以所需精度的10*数,然后可以再次应用下面的代码。
#include <stdio.h>
int main()
{
int aNumber = 500;
int gResult = 0;
int aLoop = 0;
int i = 0;
for(i = 0; i < aNumber; i++)
{
if(aLoop == 3)
{
gResult++;
aLoop = 0;
}
aLoop++;
}
printf("Reulst of %d / 3 = %d", aNumber, gResult);
return 0;
}
#include <stdio.h>
typedef struct { char a,b,c; } Triple;
unsigned long div3(Triple *v, char *r) {
if ((long)v <= 2)
return (unsigned long)r;
return div3(&v[-1], &r[1]);
}
int main() {
unsigned long v = 21;
int r = div3((Triple*)v, 0);
printf("%ld / 3 = %d\n", v, r);
return 0;
}
这应该适用于任何除数,而不仅仅是3。目前仅适用于unsigned,但将其扩展到signed应该没有那么困难。
#include <stdio.h>
unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do {
one = ~two & bor;
two ^= bor;
bor = one<<1;
} while (one);
return two;
}
unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;
if (!bot || top < bot) return 0;
for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;
for (result=0; shift--; bot >>= 1 ) {
result <<=1;
if (top >= bot) {
top = sub(top,bot);
result |= 1;
}
}
return result;
}
int main(void)
{
unsigned arg,val;
for (arg=2; arg < 40; arg++) {
val = bitdiv(arg,3);
printf("Arg=%u Val=%u\n", arg, val);
}
return 0;
}