掛け算の場合は
5 * 10 = 0b101 * 0b1010
= 0b101 * (2^3 + 2^1)
= (0b101 << 3) + (0b101 << 1) = 0b110010 = 50
で計算できるのは分かるのですが、5/3などを計算する場合どうすればいいのか思い当たらないので説明いただければと思います。 そのまま割る方法でも、1/3をバイナリで表現する方法でも大丈夫です(5 * 1/3 と出来るので)。
スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。すぐ登録できます。
登録してこのコミュニティに参加する下記コードは、割り算の筆算アルゴリズムを2進数でそのまま実装したものです。(C言語を使用)
void div(int n, int d)
{
int m = 1, q = 0;
while (d <= n) {
d <<= 1;
m <<= 1;
}
while (1 < m) {
d >>= 1;
m >>= 1;
if (n >= d) {
n -= d;
q |= m;
}
}
// q=商 / n=余り
}
LiveDemo: http://melpon.org/wandbox/permlink/blNO0ai7MChwg4a0
実用性がまるでありませんが、ビット演算子のみを利用した除算の例です。
+
, -
, 比較演算子, ループは使用していません。
#include <stdio.h>
char add(char a, char b)
{
char r = 0;
char n = 0;
r |= (a & 0x1) ^ (b & 0x1);
n = (a & 0x1) & (b & 0x1);
r |= (((a >> 1) & 0x1) ^ ((b >> 1) & 0x1) ^ n) << 1;
n = (((a >> 1) & 0x1) & ((b >> 1) & 0x1)) | (((a >> 1) & 0x1) & n) | (n & ((b >> 1) & 0x1));
r |= (((a >> 2) & 0x1) ^ ((b >> 2) & 0x1) ^ n) << 2;
n = (((a >> 2) & 0x1) & ((b >> 2) & 0x1)) | (((a >> 2) & 0x1) & n) | (n & ((b >> 2) & 0x1));
r |= (((a >> 3) & 0x1) ^ ((b >> 3) & 0x1) ^ n) << 3;
n = (((a >> 3) & 0x1) & ((b >> 3) & 0x1)) | (((a >> 3) & 0x1) & n) | (n & ((b >> 3) & 0x1));
r |= (((a >> 4) & 0x1) ^ ((b >> 4) & 0x1) ^ n) << 4;
n = (((a >> 4) & 0x1) & ((b >> 4) & 0x1)) | (((a >> 4) & 0x1) & n) | (n & ((b >> 4) & 0x1));
r |= (((a >> 5) & 0x1) ^ ((b >> 5) & 0x1) ^ n) << 5;
n = (((a >> 5) & 0x1) & ((b >> 5) & 0x1)) | (((a >> 5) & 0x1) & n) | (n & ((b >> 5) & 0x1));
r |= (((a >> 6) & 0x1) ^ ((b >> 6) & 0x1) ^ n) << 6;
n = (((a >> 6) & 0x1) & ((b >> 6) & 0x1)) | (((a >> 6) & 0x1) & n) | (n & ((b >> 6) & 0x1));
r |= (((a >> 7) & 0x1) ^ ((b >> 7) & 0x1) ^ n) << 7;
return r;
}
char sub(char a, char b)
{
return add(a, add(~b, 1));
}
char cmp(char a, char b, char c)
{
return (~(add(~add(a, b), add(c, 1)) >> 7)) & 0x1;
}
char mask(char a)
{
return (a | a << 1 | a << 2 | a << 3 | a << 4 | a << 5 | a << 6 | a << 7);
}
char ds(char *sum, char *d, char *r, char a, char b)
{
char c = cmp(*sum, b, a); *d = add(*d, c); *sum = add(*sum, b & mask(c)); *r = sub(*r, b & mask(c));
}
char ds8(char *sum, char *d, char *r, char a, char b)
{
ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b);
ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b);
}
char ds128(char *sum, char *d, char *r, char a, char b)
{
ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
}
char div(char a, char b, char *r)
{
char sum = 0, d = 0;
*r = a;
ds128(&sum, &d, r, a, b);
return d;
}
int main(void) {
int a, b;
char reminder, division;
scanf("%d / %d", &a, &b);
division = div(a, b, &reminder);
printf("%d / %d = %d (%d)", a, b, division, reminder);
return 0;
}
+
はビット演算子ではないけど、+
,-
, あるいは比較演算子は使用可?+
、-
はビットだけでの実装が簡単なんで使っていただいて大丈夫です。比較演算子も大丈夫ですが、出来れば割り算に使ってる数字本体に対してはさけていただければ