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;
}
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;
}
#include <stdio.h>
#include <math.h>
int main()
{
int number = 8;//Any +ve no.
int temp = 3, result = 0;
while(temp <= number){
temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result, 1, 1);
}
printf("\n\n%d divided by 3 = %d\n", number, result);
}
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;
}
To build:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Sample execution:
$ ./main
Enter a number: 100
100 / 3 = 33
111
通过使用 eval 和字符串连接来使用 / 运算符"behind the scenes"是否会作弊？
例如，在Javacript，你可以做到
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
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;
}
// 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 + b
n / 3 = a + (a + b) / 3
所以 sum += a ， n = a + b 和迭代
当 a == 0 (n < 4) ， sum += floor(n / 3); ，即1， if n == 3, else 0
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);
}
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}
2
以下脚本生成一个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));
}
''')
4
这是我的解决方案：
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 + ...
#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;
}
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;
5
这真的很容易 .
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;
// 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
}
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)
}
30 回答
首先，我想出了 .
EDIT: 抱歉，我没注意到标签
C. 但你可以使用关于字符串格式的想法，我猜...这种方法怎么样（c＃）？
又一个解决方案 . 这应该处理除int的最小值之外的所有整数（包括负整数），这需要作为硬编码异常处理 . 这基本上通过减法除法，但仅使用位运算符（shift，xor，＆和补码） . 为了更快的速度，它减去3 *（减少2的幂） . 在c＃中，它每毫秒执行大约444个DivideBy3调用（1,000,000个分频为2.2秒），所以不是非常慢，但没有像简单的x / 3那样快 . 相比之下，Coodey的优秀解决方案比这个快5倍 .
这是c＃，因为这是我的方便，但与c的差异应该是次要的 .
使用fma() library function的解决方案适用于任何正数：
See my another answer .
在PHP中使用BC Math：
MySQL （这是Oracle的采访）
Pascal:
x86-64 assembly language:
您可以使用（依赖于平台的）内联汇编，例如，对于x86：(also works for negative numbers)
用Pascal编写程序并使用
DIV运算符 .由于问题标记为c，您可以在Pascal中编写一个函数并从C程序中调用它;这样做的方法是系统特定的 .
但这是一个适用于我的Ubuntu系统的示例，其中安装了Free Pascal
fp-compiler软件包 . （我这样做是因为完全错位的固执;我没有声称这是有用的 . ）divide_by_3.pas ：
main.c ：
To build:
Sample execution:
通过使用
eval和字符串连接来使用/运算符"behind the scenes"是否会作弊？例如，在Javacript，你可以做到
没有反复核对这个答案是否已经发布 . 如果程序需要扩展为浮点数，则可以将数字乘以10 *所需的精度数，然后再次应用以下代码 .
这适用于任何除数，而不仅仅是三个 . 目前仅用于未签名，但将其扩展为签名应该不那么困难 .
要将32位数除以3，可将其乘以
0x55555556，然后取64位结果的高32位 .现在剩下要做的就是使用位操作和移位来实现乘法......
（注意：请参阅下面的编辑2以获得更好的版本！）
这并不像听起来那么棘手，因为你说“不使用[..]
+[..] operators ” . 如果您想禁止同时使用+字符，请参阅下文 .然后只要说
div_by(100,3)将100除以3.编辑：你也可以继续替换运营商：
编辑2：稍微快一点的版本，不使用包含 - ，*，/，％字符的任何运算符 .
我们使用
add函数的第一个参数，因为我们不能在不使用*字符的情况下表示指针的类型，除了函数参数列表，其中语法type[]与type* const相同 .FWIW，您可以使用类似的技巧轻松实现乘法函数，以使用AndreyT提出的
0x55555556技巧：使用计数器是一个基本解决方案
执行模数函数也很容易，检查注释 .
这是simple function，它执行所需的操作 . 但它需要
+运算符，所以你要做的只是用位运算符添加值：正如吉姆所评论的那样有效，因为：
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这是基数2中的经典除法算法：
使用cblas，作为OS X的Accelerate框架的一部分 .
既然它来自Oracle，那么预先计算出答案的查找表怎么样呢 . :-D
以下脚本生成一个C程序，可以在不使用运算符
* / + - %的情况下解决问题：这是我的解决方案：
首先，请注意
现在，其余的都很简单！
现在我们所要做的就是将这些位移值加在一起！哎呀！我们不能添加，所以相反，我们必须使用逐位运算符编写一个add函数！如果你熟悉逐位运算符，我的解决方案看起来应该很简单......但是如果你不是，我会在最后看一个例子 .
另外需要注意的是，首先我向左移动30！这是为了确保分数不会四舍五入 .
它只是随身携带你小时候学到的东西！
这个实现 failed 因为我们无法添加等式的所有项：
假设
div_by_3(a)= x的重新连接，然后x <= floor(f(a, i)) < a / 3. 当a = 3k时，我们得到了错误的答案 .白痴状况需要一种愚蠢的解决方案：
如果还需要小数部分，只需将
result声明为double并将fmod(number,divisor)的结果添加到其中 .Explanation of how it works
fwrite写入number个字节（上例中的数字为123456） .rewind将文件指针重置为文件的前面 .fread从文件中读取长度为divisor的number"records"的最大值，并返回它读取的元素数 .如果你写30个字节，然后以3为单位读回文件，你得到10“单位” . 30/3 = 10
在Setun computer上很容易实现 .
要将整数除以3，shift right by 1 place .
我不确定是否可以在这样的平台上实现一致的C编译器 . 我们可能不得不稍微延长规则，比如将“至少8位”解释为“能够至少保持-128到127之间的整数” .
好吧，我想我们都同意这不是一个现实世界的问题 . 所以只是为了好玩，这里是如何使用Ada和多线程来做到这一点：
这真的很容易 .
（为了简洁起见，我当然省略了一些程序 . ）如果程序员厌倦了全部输入，我肯定他或她可以编写一个单独的程序来为他生成它 . 我碰巧知道某个操作员
/，这将极大地简化他的工作 .使用itoa转换为基数3字符串 . 删除最后一个trit并转换回基数10 .
我认为正确的答案是：
为什么我不使用基本操作员进行基本操作？
使用Hacker's Delight Magic number calculator
其中fma是
math.h标头中定义的标准库函数 .第一：
然后弄清楚如何解决x /（1 - y）：
y = 1/4：
虽然它使用了
+，但有人已经通过按位运算实现了add