#5
by かずま » 6年前
a + b は、a に 1 を b回足したもの。
a * b は、a を b個足したもの。
そんなことをしたら、b が 10 の場合と、
10億の場合で、計算時間に大きな差が出ます。
CPUの設計者に申し訳なく思います。
計算時間が一定になるようにしてみました。
コード:
#include <stdio.h>
int full_adder(int a, int b, int c, int *sum)
{
*sum = a ^ b ^ c;
return a & b | b & c | c & a;
}
int add(int a, int b)
{
int sum = 0, carry = 0, s;
for (int i = 0; i < 32; i++) {
carry = full_adder(a >> i & 1, b >> i & 1, carry, &s);
sum |= s << i;
}
return sum;
}
int mul(int a, int b)
{
int sum = 0;
for (int i = 0; i < 32; i++)
if (b >> i & 1) sum = add(sum, a << i);
return sum;
}
int calc(int x)
{
return mul(add(x, 5), 3);
}
int main(void)
{
int n;
while (printf("n: "), scanf("%d", &n) == 1)
printf(" (n+5)*3: %d\n", calc(n));
}
ビット演算の and, or, exclusive or, shift と
整数の increment しか使っていません。
実行結果
コード:
n: 5
(n+5)*3: 30
n: 0
(n+5)*3: 15
n: -5
(n+5)*3: 0
n: -10
(n+5)*3: -15
n: .
a + b は、a に 1 を b回足したもの。
a * b は、a を b個足したもの。
そんなことをしたら、b が 10 の場合と、
10億の場合で、計算時間に大きな差が出ます。
CPUの設計者に申し訳なく思います。
計算時間が一定になるようにしてみました。
[code=c]
#include <stdio.h>
int full_adder(int a, int b, int c, int *sum)
{
*sum = a ^ b ^ c;
return a & b | b & c | c & a;
}
int add(int a, int b)
{
int sum = 0, carry = 0, s;
for (int i = 0; i < 32; i++) {
carry = full_adder(a >> i & 1, b >> i & 1, carry, &s);
sum |= s << i;
}
return sum;
}
int mul(int a, int b)
{
int sum = 0;
for (int i = 0; i < 32; i++)
if (b >> i & 1) sum = add(sum, a << i);
return sum;
}
int calc(int x)
{
return mul(add(x, 5), 3);
}
int main(void)
{
int n;
while (printf("n: "), scanf("%d", &n) == 1)
printf(" (n+5)*3: %d\n", calc(n));
}
[/code]
ビット演算の and, or, exclusive or, shift と
整数の increment しか使っていません。
実行結果
[code=text]
n: 5
(n+5)*3: 30
n: 0
(n+5)*3: 15
n: -5
(n+5)*3: 0
n: -10
(n+5)*3: -15
n: .
[/code]