この記事では、longやintでは桁あふれしてしまう、大きな文字列の整数をそのまま文字列の2進数に変換する方法を解説します。
コードは競技プロでよく使われるC++とPythonを使ってます。
10進数を2進数に変換する方法（整数表現から計算）
まずは整数として10進数を2進数に変換する方法を解説します。
整数として、10進数を2進数に変換するには、10進数の数字を2で割り続けて（2回目以降はその商を割る）、割った時の余りを小さい位から並べていきます。これを商が0になるまで続けると2進数の表現が得られます。
行う処理としては「2で割った時の余りを計算」「2で割った時の商を計算」の2つですね。
例えば10進数の11を2進数に変換してみます。
11 / 2 = 5・・・1 （商：5 余り：1）
5 / 2 = 2・・・1（商：2 余り：1）
2 / 2 = 1・・・0（商：1 余り：0）
1 / 2 = 0・・・1（商：1 余り：1 ※商が0になったのでここで終わる）
余りを小さい位から並べると1011となり、10進数の11の2進数表現は1011になると分かります。
C++とPythonのコードはそれぞれ以下のようになります。
#include <bits/stdc++.h>
std::string decimal2binary(int decimal) {
if (decimal == 0)
return "0";
std::string s_binary;
while (decimal) {
s_binary += std::to_string(decimal % 2); // 2で割った余り文字列として足しこむ
decimal /= 2; // 商を計算し、それでdecimalを上書き
}
// 位が逆になっているので反転させる
std::reverse(s_binary.begin(), s_binary.end());
return s_binary;
}
int main () {
int decimal = 11;
std::cout << decimal2binary(decimal) << std::endl;
return 0;
}
def decimal2binary(decimal):
if (decimal == 0):
return '0'
s_binary = ''
while decimal:
s_binary += str(decimal % 2) # 2で割った余り文字列として足しこむ
decimal //= 2 # 商を計算し、それでdecimalを上書き
# 位が逆になっているので反転させる
s_binary = s_binary[::-1]
return s_binary
if __name__ == '__main__':
decimal = 11
print(decimal2binary(decimal))
10進数を2進数に変換する方法（文字列表現から計算 – 事前準備）
次の2つの処理を文字列で行うことが出来れば、文字列で10進数を2進数に変換できますね。
・「2で割った余りを計算」
・「2で割った商を計算」
それぞれ解説します。
2で割った余りを文字列で計算
2で割った余りは文字列の10進数の末尾が偶数なら0、奇数なら1と判定できますね。なので10進数の文字列の末尾だけ取り出し、整数に変換して2で割った余りを求めたらいいですね。
コードはこんな感じになります。
7行目は見慣れないかもしれませんが、’0’はchar型でchar型の文字の数値表現は文字コードで連続しているので、’0’を引くことでchar型からint型の数値表現が得られます。（例えば’1′-‘0’=1、’3’-‘0’=3となります。）
#include <bits/stdc++.h>
/**
* 文字列の10進数を2で割った余りをcharで返す
*/
int remainder(std::string& s_decimal) {
int decimal = s_decimal.back() - '0';
return decimal%2;
}
int main () {
std::string s_decimal = "10";
std::cout << remainder(s_decimal) << std::endl;
return 0;
}
"""文字列の10進数を2で割った余りを文字列で返す
"""
def remainder(s_decimal):
decimal = ord(s_decimal[-1]) - ord('0')
return decimal%2
if __name__ == '__main__':
sdecimal = '10'
print(remainder(s_decimal))
2で割った商を文字列で計算
流れとしては、文字列の10進数の上位の桁を順番に2で割っていき、それぞれの桁の商を求めます。それぞれの桁の商を求めるときに、その桁が奇数の場合一つ下の桁に5を足しこむのがポイントです。
言葉の説明だけでは難しいので、実際のプログラムに沿って”1234″を2で割ってみます。
1. “1234”の’1’を取り出して、2で割り0（商）を取得、それに0（add）を足して新しい数0を取得。0をcharに変換して、sDiviedBy2に足して”0″にする。下に位に足す値を計算し、その結果5をaddに代入。
2. “1234”の’2’を取り出して、2で割り1（商）を取得、それに5（add）を足して新しい数6を取得。1をcharに変換して、sDiviedBy2に足して”06″にする。下に位に足す値を計算し、その結果0をaddに代入。
3. “1234”の’3’を取り出して、2で割り1（商）を取得、それに0（add）を足して新しい数1を取得。1をcharに変換して、sDiviedBy2に足して”061″にする。下に位に足す値を計算し、その結果5をaddに代入。
4. “1234”の’4’を取り出して、2で割り2（商）を取得、それに5（add）を足して新しい数7を取得。7をcharに変換して、sDiviedBy2に足して”0617″にする。下に位に足す値を計算し、その結果0をaddに代入。
5. 最後に先頭の’0’を削除し、文字列の10進数を2で割った時の商が計算できました！！
#include <bits/stdc++.h>
/**
* 文字列の10進数を2で割った商を文字列で返す
*/
std::string divBy2(std::string& s_decimal) {
int add = 0; // 下位の桁に足しこむ用の値を保持
std::string sDividedBy2 = ""; // 2で割った後の商を保持
// 上の位桁から順番に以下のこと行う
for (char c : s_decimal) {
int d = (c - '0') / 2 + add; // 1. 2で割った時の新しい数を計算
sDividedBy2 += d + '0'; // 2. 1.の整数表現を文字表現に変換して上の桁から足す
add = (c - '0') % 2 * 5; // 3. 下位の桁に足す値を計算
}
// 先頭が'0'なら削除
if (sDividedBy2.length() > 1 && sDividedBy2[0] == '0')
sDividedBy2 = sDividedBy2.substr(1);
return sDividedBy2;
}
int main() {
std::string s_decimal = "1234";
std::cout << divBy2(s_decimal) << std::endl;
}
"""文字列の10進数を文字列の2進数に変換
"""
def div_by2(s_decimal):
add = 0 # 下位の桁に足しこむ用の値を保持
s_div_by2 = '' # 2で割った後の商を保持
# 上位の桁から順番に以下のことを行う
for c in s_decimal:
d = (ord(c) - ord('0')) // 2 + add # 1. 2で割った時の新しい数を計算,その際上位の桁を割ったことによる値を足す
s_div_by2 += str(d) # 2. 1.の整数表現を文字表現に変換して上の桁から足す
add = (ord(c) - ord('0')) % 2 * 5 # 3. 下位の桁に足す値を計算
# 先頭から'0'なら削除
if len(s_div_by2) > 1 and s_div_by2[0] == '0':
s_div_by2 = s_div_by2[1:]
return s_div_by2
if __name__ == '__main__':
print(div_by2('1234'))
10進数の文字列を2進数の文字列に変換
10進数を2進数に変換する方法（整数表現から計算）の2で割った時の商と余りを求めているところを、それぞれ文字列で商と余りを求める処理に置き換えれればいいですね。
C++とPythonのコードは以下のようになります。
C++のコードは39行目、40行目で文字列として商と余りを求めています。
Pythonのコードでは、31行目と32行目で文字列として商と余りを求めています。
#include <bits/stdc++.h>
/**
* 文字列の10進数を2で割った余りをcharで返す
*/
char remainder(std::string& s_decimal) {
int decimal = s_decimal.back() - '0';
return (decimal%2 + '0');
}
/**
* 文字列の10進数を2で割った商を文字列で返す
*/
std::string divBy2(std::string& s_decimal) {
int add = 0;
std::string sDividedBy2 = "";
for (char c : s_decimal) {
int d = (c - '0') / 2 + add;
sDividedBy2 += d + '0';
add = (c - '0') % 2 * 5;
}
// 先頭が'0'なら削除
if (sDividedBy2.length() > 1 && sDividedBy2[0] == '0')
sDividedBy2 = sDividedBy2.substr(1);
return sDividedBy2;
}
/**
* 文字列の10進数を文字列の2進数に変換
*/
std::string decimal2binary(std::string s_decimal) {
if (s_decimal == "0")
return "0";
std::string s_binary;
while (s_decimal != "0") {
s_binary += remainder(s_decimal);
s_decimal = divBy2(s_decimal);
}
// 位が逆になっているので反転させる
std::reverse(s_binary.begin(), s_binary.end());
return s_binary;
}
int main() {
std::string s_decimal = "1234";
std::cout << decimal2binary(s_decimal) << std::endl;
return 0;
}
"""文字列の10進数を2で割った商を文字列で返す
"""
def div_by2(s_decimal):
add = 0
s_div_by2 = ''
for c in s_decimal:
d = (ord(c) - ord('0')) // 2 + add
s_div_by2 += str(d)
add = (ord(c) - ord('0')) % 2 * 5
# 先頭から'0'なら削除
if len(s_div_by2) > 1 and s_div_by2[0] == '0':
s_div_by2 = s_div_by2[1:]
return s_div_by2
"""文字列の10進数を2で割った余りを文字列で返す
"""
def remainder(s_decimal):
decimal = ord(s_decimal[-1]) - ord('0')
return str(decimal%2)
"""文字列の10進数を文字列の2進数に変換
"""
def decimal2binary(s_decimal):
if (s_decimal == '0'):
return '0'
s_binary = ''
while s_decimal != '0':
s_binary += remainder(s_decimal)
s_decimal = div_by2(s_decimal)
# 位が逆になっているので反転させる
s_binary = s_binary[::-1]
return s_binary
if __name__ == '__main__':
print(div_by2('1234'))
