問題
今回は、この問題の解答コードを書く。
これは、0 以上100以下の整数が2個半角空白区切りで与えられ、これらの整数の和を出力することが求められる問題である。
これは非常に基本的な問題であるため、他の場所でも同様の問題が出題されている可能性がある。
整数を足す方法
半加算器
1ビットの整数同士の足し算は、「半加算器」を用いて行うことができる。
「半加算器」は、1ビットの入力を2個受け取り、それらの和を「加算結果」と「繰り上がり」の出力で表現する回路である。
「半加算器」の入力と出力の関係 (真理値表) は、以下のようになる。
| 入力A | 入力B | 加算結果 | 繰り上がり |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
「加算結果」は入力Aと入力Bの排他的論理和 (XOR)、「繰り上がり」は入力Aと入力Bの論理積 (AND) を出力することで、これを実現できる。
全加算器
「全加算器」は、1ビットの入力を3個受け取り、それらの和を「加算結果」と「繰り上がり」の出力で表現する回路である。
「半加算器」と同様の2個の整数に加え、もう1ビット受け取れるようにしたことで、他の「全加算器」や「半加算器」の「繰り上がり」を受け取って加えることができる。
「全加算器」の入力と出力の関係 (真理値表) は、以下のようになる。
| 入力A | 入力B | 入力C | 加算結果 | 繰り上がり |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
「加算結果」は、入力A・入力B・入力Cのうち「1」であるものが奇数個のとき「1」、偶数個のとき「0」となる。
すなわち、「加算結果」は入力A・入力B・入力Cの排他的論理和 (XOR) として表せる。
「繰り上がり」は、入力A・入力B・入力Cのうち「1」であるものが2個以上のとき「1」、1個以下のとき「0」となる。
すなわち、入力A・入力B・入力Cの中から2個を選ぶ組み合わせのいずれかの論理積 (AND) が「1」のとき「1」、すべての論理積 (AND) が「0」のとき「0」として表せる。
これは、これらの論理積の論理和 (OR) をとったものである。
nビットの整数の加算
$n$ ビットの整数の加算は、半加算器を $1$ 個、全加算器を $n-1$ 個、数珠繋ぎにすることで実現できる。
加算結果は $n+1$ ビットになる。
このような「数珠繋ぎ」では、下位の計算結果 (特に、繰り上がり) が全て出揃わないと上位の計算ができないため、効率が悪い。
そのため電気回路を設計する際は高速化のための工夫をすることがあるが、今回はこの効率の悪さは問題にならないため、簡単に実現できる「数珠繋ぎ」を用いる。
今回は、0以上100以下の整数同士を加算するので、入力は7ビットの整数2個、出力は8ビットの整数1個である。
以下の図では、それぞれの事柄を以下の表記で表す。
| 事柄 | 表記 |
|---|---|
| 入力の整数A (7ビット) | 下位(LSB)から順に A0, A1, ... , A6 |
| 入力の整数B (7ビット) | 下位(LSB)から順に B0, B1, ... , B6 |
| 出力の整数 (8ビット) | 下位(LSB)から順に S0, S1, ... , S7 |
| 半加算器 | HA |
| 全加算器 | FA |
| 半加算器の入力 | A, B |
| 全加算器の入力 | A, B, C |
| 半加算器・全加算器の加算結果 | S |
| 半加算器・全加算器の繰り上がり | T |
半加算器を表す HA は Half Adder の、
全加算器を表す FA は Full Adder の略である。
これは、筆算による足し算を2進数で行う操作に相当する。
C99の演算子
C99 (C言語の規格の一つ) には、以下の演算子 (全48個) がある。
ここでは、主に整数同士の演算における意味を記載し、細かい点は省略する。
四則演算
| 演算子 | 意味 |
|---|---|
a++ |
a の値を1増やし、増やす前の値を返す |
++a |
a の値を1増やし、増やした後の値を返す |
a-- |
a の値を1減らし、減らす前の値を返す |
--a |
a の値を1減らし、減らした後の値を返す |
a + b |
a と b の和 |
a - b |
a から b を引いた差 |
a * b |
a と b の積 |
a / b |
a を b で割った商 |
a % b |
a を b で割った余り |
a += b |
a と b の和を a に代入する |
a -= b |
a から b を引いた差を a に代入する |
a *= b |
a と b の積を a に代入する |
a /= b |
a を b で割った商を a に代入する |
a %= b |
a を b で割った余りを a に代入する |
ビット演算
| 演算子 | 意味 |
|---|---|
~a |
a の値の各ビットを反転した値 |
a & b |
a と b の各ビットの論理積 (AND) |
a | b |
a と b の各ビットの論理和 (OR) |
a ^ b |
a と b の各ビットの排他的論理和 (XOR) |
a << b |
a を b ビット左シフトした値 |
a >> b |
a を b ビット右シフトした値 |
a &= b |
a と b の各ビットの論理積 (AND) を a に代入する |
a |= b |
a と b の各ビットの論理和 (OR) を a に代入する |
a ^= b |
a と b の各ビットの排他的論理和 (XOR) を a に代入する |
a <<= b |
a を b ビット左シフトした値を a に代入する |
a >>= b |
a を b ビット右シフトした値を a に代入する |
比較
| 演算子 | 意味 |
|---|---|
a == b |
a と b の値が等しいなら1、そうでないなら0 |
a != b |
a と b の値が等しくないなら1、そうでないなら0 |
a < b |
a の値が b 未満なら1、そうでないなら0 |
a <= b |
a の値が b 以下なら1、そうでないなら0 |
a > b |
a の値が b 超なら1、そうでないなら0 |
a >= b |
a の値が b 以上なら1、そうでないなら0 |
論理演算
| 演算子 | 意味 |
|---|---|
!a |
a の値が0以外なら0、0なら1 (論理否定) |
a && b |
a と b の両方が0以外なら1、そうでなければ0 (論理AND) |
a || b |
a と b のうち1個以上が0以外なら1、そうでなければ0 (論理OR) |
その他
| 演算子 | 意味 |
|---|---|
+a |
a の値 |
-a |
a の値の符号を反転した値 |
*a |
ポインタ a が指す値 |
&a |
a を指すポインタ |
sizeof(type) |
型 type のサイズ (バイト数) |
(type)a |
a を型 type に変換 (キャスト) した値 |
(type){ initializer-list } |
型 (主に配列や構造体) type の値(compound literals) |
a = b |
b の値を a に代入する |
a(argument-list) |
関数 a を引数 argument-list で呼び出す |
a[b] |
配列 a の b 番目の要素 |
a.member |
構造体 a のメンバ member
|
a->member |
ポインタ a が指す構造体のメンバ member
|
a , b |
a を評価し、その後 b を評価する |
a ? b : c |
a の値が0以外なら b、0なら c
|
sizeof 演算子は、型 type をとる sizeof(type) の形式で用いる以外に、式 a をとる sizeof a の形式で用いることもできる。
C11では、型 type のアライメント要件を返す演算子 _Alignof(type) が追加されている。
加算器による演算を模した足し算の実装
ソースコード
#include <stdio.h>
#include <limits.h>
int add0(int* carry, int a, int b) {
*carry = a + b >= 2;
return a != b;
}
int add1(int* carry_out, int a, int b, int c) {
*carry_out = (a && b) || (b && c) || (c && a);
a ^= b ^ c;
return +a;
}
int add2(int* carry_out, int a, int b, int c) {
int ab, bc, ca;
ab = a; ab -= -b;
bc = 0;
if (b) bc--;
if (c) --bc;
ca = c; ca += a;
*carry_out = !!((ab == 2) + (bc <= -2) + (1 < ca));
return (a + b + c) % 2;
}
struct add3_ret {
int result;
int carry;
};
struct add3_ret add3(int a, int b, int c) {
int ab, bc, ca;
ab = a; ab *= b;
bc = ~(~b | ~c);
ca = c; ca <<= a;
return (struct add3_ret){ (a != b) - c ? 1 : 0, ab || bc || (ca & 2) };
}
int main(void) {
int a, b;
int a_bits[7], b_bits[7], ans_bits[8];
int i, carry;
struct add3_ret ret;
int ans = 0;
if (scanf("%d%d", &a, &b) != 2) return 1;
a_bits[0] = ((unsigned int)a << (sizeof(unsigned int) * CHAR_BIT - 1)) > 0;
a_bits[1] = a / 2; a_bits[1] %= 2;
a_bits[2] = a >> 2; a_bits[2] &= 1;
a_bits[3] = a % 16; a_bits[3] /= 8;
a_bits[4] = a % 32; a_bits[4] >>= 4;
a_bits[5] = (a >> 5) & 1;
a_bits[6] = a >> 6;
for (i = 0; i < 7; i++) {
b_bits[i] = (b >> i) & 1;
}
ans_bits[0] = add0(&carry, a_bits[0], b_bits[0]);
ans_bits[1] = add1(&carry, a_bits[1], b_bits[1], carry);
ans_bits[2] = add2(&carry, a_bits[2], b_bits[2], carry);
ret = add3(a_bits[3], b_bits[3], carry);
ans_bits[3] = (&ret)->result;
ret = add3(a_bits[4], b_bits[4], ret.carry);
ans_bits[4] = ret.result;
ans_bits[5] = add2(&carry, a_bits[5], b_bits[5], ret.carry);
ans_bits[6] = add1(&ans_bits[7], a_bits[6], b_bits[6], carry);
for (i = 0, ans = 0; i < 8; ++i) {
ans |= ans_bits[i] << i;
}
printf("%d\n", ans);
return 0;
}
提出 #57107289 - C++入門 AtCoder Programming Guide for beginners (APG4b)
解説
add0
0 または 1 の数値を2個受け取り、半加算器の動作を模倣する関数である。
*carry = a + b >= 2;
a と b が両方 1 の場合は、足すと 2 以上になるので、繰り上がりが 1 になる。
そうでない場合は、足すと 2 未満になるので、繰り上がりが 0 になる。
return a != b;
a と b の値が異なる場合は 1、同じ場合は 0 を返している。
これは、a と b のXORと同じなので、加算結果を求めることができる。
add1
0 または 1 の数値を3個受け取り、全加算器の動作を模倣する関数である。
*carry_out = (a && b) || (b && c) || (c && a);
論理演算を用いて、「a・b・c のうちいづれか2個が 1 なら 1」を素直に表現している。
a ^= b ^ c;
return +a;
まず b と c のXORを求め、それを a とXORすることで、3個の数値のXORを求めている。
add2
0 または 1 の数値を3個受け取り、全加算器の動作を模倣する関数である。
int ab, bc, ca;
ab = a; ab -= -b;
bc = 0;
if (b) bc--;
if (c) --bc;
ca = c; ca += a;
*carry_out = !!((ab == 2) + (bc <= -2) + (1 < ca));
2個の数値が両方1かどうかを、それぞれ変数 ab・bc・ca を用いて調べている。
両方1の場合、ab と ca は 2 に、bc は -2 になる。
これらの値になっているかを、比較演算子を用いて調べている。
それらの結果を加算し、論理否定を2回行うことで、論理OR (比較結果が1のものがあれば1、なければ0) を実現している。
return (a + b + c) % 2;
単純に加算を行い、2で割った余りを求めることで1が奇数個あるか偶数個あるかを調べている。
add3
0 または 1 の数値を3個受け取り、全加算器の動作を模倣する関数である。
また、結果は構造体を用いて返している。
int ab, bc, ca;
ab = a; ab *= b;
bc = ~(~b | ~c);
ca = c; ca <<= a;
2個の数値が両方1かどうかを、それぞれ変数 ab・bc・ca を用いて調べている。
ab は、乗算を用いて両方1かを判定している。
bc は、ビットANDをド・モルガンの法則を用いて変換した計算式を用いている。
ca は、「ビットをずらす」「ずらす対象のビットが1」が両方成り立つなら真、そうでないなら偽になるようにしている。
return (struct add3_ret){ (a != b) - c ? 1 : 0, ab || bc || (ca & 2) };
加算結果は、等価比較と減算をそれぞれXORのかわりに用いて求めている。
繰り上がりは、2個の数値が両方1かどうかの判定結果の論理ORをとることで求めている。
main
以下の処理を行っている。
- 入力を読み込む
- 入力の数値を1ビットずつに分割する
- ビット同士の足し算を行い、出力する数値の各ビットを求める
- 出力の各ビットを合体し、1個の数値にする
- 出力を行う
「入力の数値を1ビットずつに分割する」処理は、基本的には
- 欲しいビットを最下位に持ってきた後、それより上のビットを0にする
- 欲しいビットより上のビットを0にした後、欲しいビットを最下位に持ってくる
のいずれかである。
a_bits[0] = ((unsigned int)a << (sizeof(unsigned int) * CHAR_BIT - 1)) > 0;
では、欲しいビットを最上位に持って行くことでそれより上のビットを追い出して消し、その後比較演算を用いて0か1の情報を得ている。
おわりに
今回は、C99の演算子を全部使って足し算の処理を行うプログラムを書いてみた。
このようなプログラムは、C言語の処理系を実装した際、そのテストに役立つ可能性がある。
しかし、今回のプログラムではカバーできていない演算子の機能 (たとえば、インクリメント・デクリメント演算子が返す値) もあり、今回のプログラムだけで十分なテストができるわけではない。