qwe*_*rtz 544
这是一个执行所需操作的简单功能.但它需要+操作员,所以你要做的只是用位运算符添加值:
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
正如吉姆所评论的那样有效,因为:
n = 4 * a + bn / 3 = a + (a + b) / 3 所以sum += a,n = a + b和迭代
什么时候a == 0 (n < 4),sum += floor(n / 3);即1,if n == 3, else 0
Mat*_*lia 434
白痴状况需要一种愚蠢的解决方案:
#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,divisor).
解释它是如何工作的
fwrite写入number字节(序号为在示例123456段).rewind 将文件指针重置为文件的前面.fread从文件中读取最大长度的number"记录" divisor,并返回它读取的元素数.如果你写30个字节,然后以3为单位读回文件,你得到10"单位".30/3 = 10
Ala*_*rry 305
log(pow(exp(number),0.33333333333333333333)) /* :-) */
nos*_*nos 205
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C function.
printf("%d\n", r.quot);
return 0;
}
moo*_*eep 111
您可以使用(平台相关的)内联汇编,例如,对于x86 :( 也适用于负数)
#include <stdio.h>
int main() {
int dividend = -42, divisor = 5, quotient, remainder;
__asm__ ( "cdq; idivl %%ebx;"
: "=a" (quotient), "=d" (remainder)
: "a" (dividend), "b" (divisor)
: );
printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder);
return 0;
}
小智 106
使用itoa转换为基数3字符串.删除最后一个trit并转换回基数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
}
bit*_*ask 57
(注意:请参阅下面的编辑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)
}
+,-,*,/,% 字符.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函数的第一个参数,因为我们不能在不使用*字符的情况下表示指针的类型,除了在函数参数列表中,语法type[]是相同的type* const.
FWIW,您可以使用类似的技巧轻松实现乘法功能,以使用AndreyT0x55555556提出的技巧:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
小智 32
这是我的解决方案:
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 + ...
现在我们所要做的就是将这些位移值加在一起!哎呀!我们不能添加,所以相反,我们必须使用逐位运算符编写一个add函数!如果你熟悉逐位运算符,我的解决方案应该看起来相当简单......但是如果你不是,我会在最后介绍一个例子.
另外需要注意的是,首先我向左移动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,我们得到错误答案.
AnT*_*AnT 25
要将32位数除以3,可将其乘以0x55555556,然后取64位结果的高32位.
现在剩下要做的就是使用位操作和移位来实现乘法......
hat*_*ica 18
又一个解决方案.这应该处理除int的min值之外的所有int(包括负int),这需要作为硬编码异常处理.这基本上通过减法除法,但仅使用位运算符(shift,xor,&和complement).为了更快的速度,它减去3*(减少2的幂).在c#中,它每毫秒执行大约444个DivideBy3调用(1,000,000个分频为2.2秒),所以不是非常慢,但没有像简单的x/3那样快.相比之下,Coodey的漂亮解决方案比这个快5倍.
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的差异应该是次要的.
the*_*rns 15
这真的很容易.
if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;
(为了简洁起见,我当然省略了一些程序.)如果程序员厌倦了全部输入,我肯定他或她可以编写一个单独的程序来为他生成它.我碰巧知道某个操作员/,这将极大地简化他的工作.
GJ.*_*GJ. 14
使用计数器是一个基本解决方案
int DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
执行模数函数也很容易,检查注释.
Eri*_*lle 11
这是基础2中的经典除法算法:
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t mod3[6] = { 0,1,2,0,1,2 };
uint32_t x = 1234567; // number to divide, and remainder at the end
uint32_t y = 0; // result
int bit = 31; // current bit
printf("X=%u X/3=%u\n",x,x/3); // the '/3' is for testing
while (bit>0)
{
printf("BIT=%d X=%u Y=%u\n",bit,x,y);
// decrement bit
int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
uint32_t r = x>>bit; // current remainder in 0..5
x ^= r<<bit; // remove R bits from X
if (r >= 3) y |= 1<<bit; // new output bit
x |= mod3[r]<<bit; // new remainder inserted in X
}
printf("Y=%u\n",y);
}
用Pascal编写程序并使用DIV运算符.
由于问题标记为c,您可以在Pascal中编写一个函数并从C程序中调用它; 这样做的方法是系统特定的.
但这是一个可以在我的Ubuntu系统上fp-compiler安装Free Pascal 软件包的示例.(我这样做是因为完全错位的固执;我没有声称这是有用的.)
divide_by_3.pas :
unit Divide_By_3;
interface
function div_by_3(n: integer): integer; cdecl; export;
implementation
function div_by_3(n: integer): integer; cdecl;
begin
div_by_3 := n div 3;
end;
end.
main.c :
#include <stdio.h>
#include <stdlib.h>
extern int div_by_3(int n);
int main(void) {
int n;
fputs("Enter a number: ", stdout);
fflush(stdout);
scanf("%d", &n);
printf("%d / 3 = %d\n", n, div_by_3(n));
return 0;
}
建立:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
样品执行:
$ ./main
Enter a number: 100
100 / 3 = 33
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}
没有反复核对这个答案是否已经发布.如果程序需要扩展为浮点数,则可以将数字乘以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>
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;
}
<?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
/通过使用eval和字符串连接使用"幕后"操作符会不会是作弊？
例如,在Javacript,你可以做到
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
首先,我想出了.
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.但你可以使用关于字符串格式的想法,我猜...
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
其中fma是标math.h头中定义的标准库函数.
以下脚本生成一个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));
}
''')
第一的：
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)
}
虽然它使用+，但有人已经通过按位运算实现了加法。