C++のstd::bitset<N>を用いた各種計算・処理を手動で実装するサンプル [unsigned]

C++のstd::bitsetを用いた各種計算・処理を手動で実装するサンプル [unsigned].md

C++のstd::bitset<N>を用いた各種計算・処理を手動で実装するサンプル [unsigned]

定義

このページ上のコードのライセンスについて

このページ上に記載されている各コードのライセンスはパブリックドメインとする

演算方向について

表記	略表記	意味
Low To High	LTH	最下位ビットから最上位ビットに向けて演算する
High To Low	HTL	最上位ビットから最下位ビットに向けて演算する
Both	(略表記なし)	LTHとHTLのどちらで計算しても問題ない

インクリメントをするサンプル

真理値表

• 最下位ビット処理用

  An	→	Xn	Cn
  0	→	1	0
  1	→	0	1

  • 補足：最下位ビットに対し+1の処理を行う

• 最下位以外のビット処理用

  An	Cn-1	→	Xn	Cn
  0	0	→	0	0
  0	1	→	1	0
  1	0	→	1	0
  1	1	→	0	1

  • 補足：下位ビットからの繰り上がり処理を行う

論理式

• 最下位ビット処理用

  • X _n = not(A_n)
  • C_n = A_n

• 最下位以外のビット処理用

  • X_n = A_n ⊕ C_n-1
  • C_n = A_n ・ C_n-1

演算方向

LTH

コード

• 変数名と論理式の表記の関連について (書式：変数名 = 論理式上の表記)
  • Cn = C_n
  • Cb = C_n-1
  • X = X_n

template <size_t N> std::bitset<N> IncrementBitset( const std::bitset<N> iA ) {

	std::bitset<N>  ox( 0 );

	bool A, X, Cn, Cb = 0;

	for ( size_t i = 0; i < N; i++ ) {

		A = iA[i];

		if ( i == 0 ) {
			X = !A;
			Cn = A;
		} else {
			X = A ^ Cb;
			Cn = A && Cb;
		}

		ox[i] = X;
		Cb = Cn;
	}

	return ox;
}

デクリメントをするサンプル

真理値表

An	Cn-1	→	Xn	Cn
0	0	→	1	0
0	1	→	0	1
1	0	→	0	1
1	1	→	1	1

• 補足：全ビットに対し1加算する処理を行う
  • 全ビットに対し1加算すると -1 (1の2の補数)を加算するのと同義な処理になる

論理式

• X _n = not(A_n ⊕ C_n-1)
• C_n = A_n + C_n-1

演算方向

LTH

コード

template <size_t N> std::bitset<N> DecrementBitset( const std::bitset<N> iA ) {

	std::bitset<N>  ox( 0 );

	bool A, X, Cn, Cb = 0;

	for ( size_t i = 0; i < N; i++ ) {
		A = iA[i];

		X = !( A ^ Cb );
		Cn = A || Cb;

		ox[i] = X;
		Cb = Cn;
	}

	return ox;
}

1ビットシフトするサンプル

• ※ std::bitset にはシフト演算子が標準で実装されているので通常はそれを利用すればよい

真理値表

An	Cn-1	→	Xn	Cn
0	0	→	0	0
0	1	→	1	0
1	0	→	0	1
1	1	→	1	1

論理式

• X _n = C_n-1
• C_n = A_n

演算方向

• 左に1ビットシフトする場合：LTH
• 右に1ビットシフトする場合：HTL

コード

• 左に1ビットシフトするLeftOneShiftBitset関数の実装サンプル

   template <size_t N> std::bitset<N> LeftOneShiftBitset( const std::bitset<N> iA ) {
  
   	std::bitset<N>  ox( 0 );
   	bool A, X, Cn, Cb = 0;
  
   	for ( size_t i = 0; i < N; i++ ) {
  
   		A = iA[i];
  
   		X = Cb;
   		Cn = A;
  
   		ox[i] = X;
   		Cb = Cn;
   	}
  
   	return ox;
   }

• 右に1ビットシフトするRightOneShiftBitset関数の実装サンプル

   template <size_t N> std::bitset<N> RightOneShiftBitset( const std::bitset<N> iA ) {
   
   	std::bitset<N>  ox( 0 );
   	bool A, X, Cn, Cb = 0;
   	
   	for ( size_t i = 0; i < N; i++ ) {
   
   		A = iA[N - 1 - i];
   
   		X = Cb;
   		Cn = A;
   
   		ox[N - 1 - i] = X;
   		Cb = Cn;
   	}
   
   	return ox;
   }

加算するサンプル

真理値表

An	Bn	Cn-1	→	Xn	Cn
0	0	0	→	0	0
0	0	1	→	1	0
0	1	0	→	1	0
0	1	1	→	0	1
1	0	0	→	1	0
1	0	1	→	0	1
1	1	0	→	0	1
1	1	1	→	1	1

論理式

• X_n
  • = not(A_n)・not(B_n)・C_n-1 + not(A_n)・B_n・not(C_n-1) + A_n・not(B_n)・not(C_n-1) + A_n・B_n・C_n-1
  • = not(A_n)・(B_n ⊕ C_n-1) + A_n・not(B_n ⊕ C_n-1)
  • = A_n ⊕ B_n ⊕ C_n-1
• C_n
  • = not(A_n)・B_n・C_n-1 + A_n・not(B_n)・C_n-1 + A_n・B_n・not(C_n-1) + A_n・B_n・C_n-1
  • = A_n・(B_n ⊕ C_n-1) + B_n・C_n-1

演算方向

LTH

コード

template <size_t N> std::bitset<N> AddBitset( const std::bitset<N> ia, const std::bitset<N> ib, const bool carry = false, bool* const pLastCarry = nullptr ) {
	std::bitset<N>  ox( 0 );

	bool a, b, x;
	bool c = 0, Cb = carry;

	for ( size_t i = 0; i < N; i++ ) {
		a = ia[i];
		b = ib[i];

		x = a ^ b ^ Cb;
		c = ( a && ( b ^ Cb ) ) || ( b && Cb );

		ox[i] = x;
		Cb = c;
	}

	if ( pLastCarry ) *pLastCarry = Cb;

	return ox;
}

減算を行うサンプル

真理値表

An	Bn	Cn-1	→	Xn	Cn
0	0	0	→	0	0
0	0	1	→	1	1
0	1	0	→	1	1
0	1	1	→	0	1
1	0	0	→	1	0
1	0	1	→	0	0
1	1	0	→	0	0
1	1	1	→	1	1

論理式

• X_n
  • = not(A_n)・not(B_n)・C_n-1 + not(A_n)・B_n・not(C_n-1) + A_n・not(B_n)・not(C_n-1) + A_n・B_n・C_n-1
  • = not(A_n)・(B_n ⊕ C_n-1) + A_n・not(B_n ⊕ C_n-1)
  • = A_n ⊕ B_n ⊕ C_n-1
• C_n
  • = not(A_n)・not(B_n)・C_n-1 + not(A_n)・B_n・not(C_n-1) + not(A_n)・B_n・C_n-1 + A_n・B_n・C_n-1
  • = not(A_n)・(B_n ⊕ C_n-1) + B_n・C_n-1

演算方向

LTH

コード

template <size_t N> std::bitset<N> MinusBitset( const std::bitset<N> ia, const std::bitset<N> ib ) {
	std::bitset<N>  ox( 0 );
	bool a, b, x;
	bool c = 0, Cb = false;

	for ( size_t i = 0; i < N; i++ ) {
		a = ia[i];
		b = ib[i];

		x = a ^ b ^ Cb;
		c = ( ( !a) && ( b ^ Cb ) ) || ( b && Cb );

		ox[i] = x;
		Cb = c;
	}

	return ox;
}

別の実装方法

A-B を計算する場合、AにBの2の補数を加算することでも実装できる。

以下、 AddBitset関数を呼び出す方法での実装例となる。

template <size_t N> std::bitset<N> MinusBitsetByAddBitset( const std::bitset<N> ia, const std::bitset<N> ib ) {
	return AddBitset( ia, ~ib, true );
}

乗算を行うサンプル

template <size_t N> std::bitset<N> MultipleBitset( const std::bitset<N> ia, const std::bitset<N> ib ) {

	std::bitset<N> ox( 0 );
	std::bitset<N> auxiliary( ia );

	for ( size_t i = 0; i < N; i++ ) {

		if ( ib[i] ) {
			ox = AddBitset( ox, auxiliary);
		}

		auxiliary = LeftOneShiftBitset( auxiliary );
	}

	return ox;
}

除算・剰余計算 を行うサンプル

• 以下コードで呼び出している関数について
  • IsLeftOrAboveBitset関数は第1パラメーターL と 第2パラメーターR を比較してL>=R であるかを判定する関数である
  • GetNumberOfDigitBitset関数は桁数を取得する関数である

template <size_t N> using pair_bitset_n = std::pair<std::bitset<N>, std::bitset<N>>;
template <size_t N> using optional_pair_bitset_n = std::optional<pair_bitset_n<N>>;

template <size_t N> optional_pair_bitset_n<N> DivisionBitset( const std::bitset<N> ia, const std::bitset<N> ib ) {


	if ( ib.none( ) ) return std::nullopt;

	if ( IsLeftOrAboveBitset( ia, ib ) == false ) {
		// ia < ib の時、商：0、あまり：ia
		return std::pair(std::bitset<N>( 0 ) , ia);
	}

	const size_t digit_ia = GetNumberOfDigitBitset( ia );
	const size_t digit_ib = GetNumberOfDigitBitset( ib );
	const size_t digit_ox = digit_ia - digit_ib + 1;

	std::bitset<N>  auxiliary( 0 );
	for ( size_t i = 0; i < digit_ib; i++ ) {
		auxiliary[digit_ib - 1 - i] = ia[digit_ia - 1 - i];
	}

	std::bitset<N>  ox( 0 );
	for ( size_t i = 0; i < digit_ox; i++ ) {

		ox[digit_ox - 1 - i] = IsLeftOrAboveBitset( auxiliary, ib );

		if ( ox[digit_ox - 1 - i]) {
			auxiliary = MinusBitset( auxiliary, ib );
		} 

		if ( ( i + 1 ) < digit_ox ) {
			auxiliary = LeftOneShiftBitset( auxiliary );
			auxiliary[0] = ia[digit_ia - digit_ib - i - 1];
		}
	}

	// ox：商、auxiliary：余り
	return std::pair( ox, auxiliary );
}

GetNumberOfDigitBitset関数の実装サンプル

template <size_t N> size_t GetNumberOfDigitBitset( const std::bitset<N> iA ) {
	size_t digit = 0;

	for ( size_t i = 0; i < N; i++ ) {
		if ( iA[i] ) digit = i;
	}

	return digit + 1;
}

IsLeftOrAboveBitset関数の実装サンプル

template <size_t N> bool IsLeftOrAboveBitset( const std::bitset<N> L, const std::bitset<N> R ) {
	bool isEqual = true;
	bool isAbove = false;
	size_t index;

	for ( size_t i = 0; ( i < N ) && isEqual; i++ ) {
		index = N - 1 - i;
		isAbove = L[index] && ( !R[index] );
		isEqual = !( L[index] ^ R[index] );
		if ( isAbove ) return true;
	}

	return isEqual;
}

文字列との変換

std::bitset<N> を 2進数文字列に変換する関数のサンプル

template <size_t N> std::string  bitset_to_binary_str( const std::bitset<N> bin ) {
	size_t msb_pos;
	for ( msb_pos = N - 1; msb_pos > 0; msb_pos-- ) {
		if ( bin[msb_pos] )break;
	}
	std::string result_string;
	for ( size_t i = 0; i <= msb_pos; i++ ) {
		result_string.push_back( ( bin[msb_pos - i] ) ? '1' : '0' );
	}
	return result_string;
}

2進数文字列から std::bitset<N>に変換する関数のサンプル

template <size_t N>  std::bitset<N>  bitset_from_binary_str( const std::string binstr ) {
	size_t bit_pos = 0;
	char c;
	std::bitset<N> result;

	for ( auto rev_it = binstr.rbegin( ); ( rev_it != binstr.rend( ) ) && ( bit_pos < N ); rev_it++ ) {
		c = *rev_it;
		if ( c == '0' ) {
			result[bit_pos] = false;
			bit_pos++;
		} else if ( c == '1' ) {
			result[bit_pos] = true;
			bit_pos++;
		} else  if ( ( c == ',' ) || ( c == ' ' ) ) {
			continue;
		} else {
			break;
		}
	}
	return result;
}

std::bitset<N> を 10進数文字列に変換する関数のサンプル

template <size_t N> std::string  bitset_to_dec_str( const std::bitset<N> bin ) {
	if ( N < 4 ) {
		std::bitset<4> bs( bin.to_ulong( ) );
		return  bitset_to_dec_str( bs );
	} else {
		const std::bitset<N>  bit_of_ten( 10 );
		std::bitset<N> auxiliary( bin );
		uint8_t current_digit_value;
		optional_pair_bitset_n<N> div_10_result;
		std::string result_string;

		do {
			div_10_result = DivisionBitset( auxiliary, bit_of_ten );
			if ( div_10_result.has_value( ) == false ) return std::string( );
			auxiliary = div_10_result.value( ).first;
			current_digit_value = div_10_result.value( ).second.to_ulong( ) & 0xff;
			result_string.push_back( '0' + current_digit_value );
		} while ( auxiliary.none( ) == false );

		std::reverse( result_string.begin( ), result_string.end( ) );
		return result_string;
	}
}

10進数文字列から std::bitset<N>に変換する関数のサンプル

template <size_t N>  std::bitset<N>  bitset_from_dec_str( const std::string binstr ) {
	std::bitset<N> result;
	if ( N < 4 ) {
		std::bitset<4> bs = bitset_from_dec_str<4>( binstr );
		for ( size_t i = 0; i < N; i++ )  result[i] = bs[i];
		return result;
	} else {
		const std::bitset<N>  bit_of_ten( 10 );
		std::bitset<N> current_digit_bitset( 0 );
		uint8_t current_digit_value;
		for ( char c : binstr ) {
			if ( c >= '0' && c<= '9' ) {
				current_digit_value = c - '0';
				current_digit_bitset[0] = current_digit_value & 1;
				current_digit_bitset[1] = current_digit_value & 2;
				current_digit_bitset[2] = current_digit_value & 4;
				current_digit_bitset[3] = current_digit_value & 8;
				result = MultipleBitset( result, bit_of_ten );
				result = AddBitset( result, current_digit_bitset );
			} else if (( c != ',' )&& ( c != ' ' )) {
				break;
			}
		}
		return result;
	}
}

std::bitset<N> を 16進数文字列に変換する関数のサンプル

template <size_t N> std::string  bitset_to_hex_str( const std::bitset<N> bin , bool upper_case  = false) {
	if ( N < 4 ) {
		std::bitset<4> bs( bin.to_ulong( ) );
		return  bitset_to_hex_str( bs );
	} else {
		std::bitset<N> auxiliary( bin );
		uint8_t current_digit_value;
		std::string result_string;

		do {
			current_digit_value = auxiliary[0] + auxiliary[1] * 2 + auxiliary[2] * 4 + auxiliary[3] * 8;
			auxiliary >>= 4;
			if(current_digit_value<10 ) result_string.push_back( '0' + current_digit_value );
			else result_string.push_back( ((upper_case)?'A':'a') + ( current_digit_value - 10 ) );
		} while ( auxiliary.none( ) == false );

		std::reverse( result_string.begin( ), result_string.end( ) );
		return result_string;
	}
}

16進数文字列から std::bitset<N>に変換する関数のサンプル

template <size_t N>  std::bitset<N>  bitset_from_hex_str( const std::string binstr ) {
	std::bitset<N> result;
	if ( N < 4 ) {
		std::bitset<4> bs = bitset_from_dec_str<4>( binstr );
		for ( size_t i = 0; i < N; i++ )  result[i] = bs[i];
		return result;
	} else {
		uint8_t current_digit_value=0;
		for ( char c : binstr ) {
			if ( c >= '0' && c <= '9' ) {
				current_digit_value = c - '0';
			} else if ( c >= 'A' && c<= 'F' ) {
				current_digit_value = 10 + c - 'A';
			} else if ( c >= 'a' && c<= 'f' ) {
				current_digit_value = 10 + c - 'a';
			} else  if ( ( c == ',' ) || ( c == ' ' ) ) {
				continue;
			}else{
				break;
			}

			result <<= 4;
			result[0] = current_digit_value & 1;
			result[1] = current_digit_value & 2;
			result[2] = current_digit_value & 4;
			result[3] = current_digit_value & 8;
		}
		return result;
	}
}

使用例サンプル

サンプル1 : 四則演算

• コード

   #define  single_separator_println(x) 	for ( size_t i = 0; i < (x); i++ )  { printf( "-" ); } printf( "\n" );
  
   enum struct NumberType {
   	Binary = 0,
   	Decimal,
   	Hexadecimal
   };
  
   template <size_t N> void Sample1( const std::string number1String, const std::string number2String, const NumberType numType = NumberType::Hexadecimal ) {
   	using bitset_local = std::bitset<N>;
   	bitset_local num1, num2, num_result;
   	optional_pair_bitset_n<N> div_result;
   	std::string num1_str, num2_str;
   	const size_t separator_len = 100;
  
   	switch ( numType ) {
   		case NumberType::Binary:
   			num1 = bitset_from_binary_str<N>( number1String );
   			num2 = bitset_from_binary_str<N>( number2String );
   			break;
   		case NumberType::Decimal:
   			num1 = bitset_from_dec_str<N>( number1String );
   			num2 = bitset_from_dec_str<N>( number2String );
   			break;
   		case NumberType::Hexadecimal:
   			num1 = bitset_from_hex_str<N>( number1String );
   			num2 = bitset_from_hex_str<N>( number2String );
   			break;
   		default:
   			return;
   	}
  
   	num1_str = bitset_to_dec_str( num1 );
   	num2_str = bitset_to_dec_str( num2 );
   	single_separator_println( separator_len );
   	printf( "bit size (std::bitset size): %zu\n\n", static_cast<size_t>( N ) );
  
   	printf( "Number1：\n\t10進数表記：%s\n\t16進数表記：%s\n\t 2進数表記：%s\n\n",
   		num1_str.c_str( ), bitset_to_hex_str( num1, true ).c_str( ), 
   		bitset_to_binary_str( num1 ).c_str( ) );
  
   	printf( "Number2：\n\t10進数表記：%s\n\t16進数表記：%s\n\t 2進数表記：%s\n",
   		num2_str.c_str( ), bitset_to_hex_str( num2, true ).c_str( ), 
   		bitset_to_binary_str( num2 ).c_str( ) );
   	single_separator_println( separator_len );
  
   	num_result = AddBitset( num1, num2 );
   	printf( "%s ＋ %s = %s\n", num1_str.c_str( ), num2_str.c_str( ),
   		bitset_to_dec_str( num_result ).c_str( ) );
  
   	num_result = MinusBitset( num1, num2 );
   	printf( "%s － %s = %s\n", num1_str.c_str( ), num2_str.c_str( ),
   		bitset_to_dec_str( num_result ).c_str( ) );
  
   	num_result = MultipleBitset( num1, num2 );
   	printf( "%s × %s = %s\n", num1_str.c_str( ), num2_str.c_str( ),
   		bitset_to_dec_str( num_result ).c_str( ) );
  
   	div_result = DivisionBitset( num1, num2 );
   	if ( div_result.has_value( ) ) {
   		printf( "%s ÷ %s = %s あまり　%s\n", num1_str.c_str( ), num2_str.c_str( ),
   			bitset_to_dec_str( div_result.value( ).first ).c_str( ), 
   			bitset_to_dec_str( div_result.value( ).second ).c_str( ) );
   	}
  
   	num_result = MinusBitset( num2, num1 );
   	printf( "\n%s － %s = %s\n", num2_str.c_str( ), num1_str.c_str( ),
   		bitset_to_dec_str( num_result ).c_str( ) );
  
   	printf( "\n" );
   }
  
   int main( void ) {
   	Sample1<8>( "1001 0101", "0110 1010", NumberType::Binary );
   	Sample1<16>( "10456", "821", NumberType::Decimal );
   	Sample1<32>( "fd6a 2396", "281 c021", NumberType::Hexadecimal );
   	Sample1<64>( "fccd 9812 cdde ffcd", "3cd dca0 6281 21dd", NumberType::Hexadecimal );
   	Sample1<128>( "c0 cfff 45d2 a2dd cc1f", "cd10 aacc b321"  , NumberType::Hexadecimal);
   	return 0;
   }

• 実行結果

   ----------------------------------------------------------------------------------------------------
   bit size (std::bitset size): 8
  
   Number1：
   		10進数表記：149
   		16進数表記：95
   		 2進数表記：10010101
  
   Number2：
   		10進数表記：106
   		16進数表記：6A
   		 2進数表記：1101010
   ----------------------------------------------------------------------------------------------------
   149 ＋ 106 = 255
   149 － 106 = 43
   149 × 106 = 178
   149 ÷ 106 = 1 あまり　43
  
   106 － 149 = 213
  
   ----------------------------------------------------------------------------------------------------
   bit size (std::bitset size): 16
  
   Number1：
   		10進数表記：10456
   		16進数表記：28D8
   		 2進数表記：10100011011000
  
   Number2：
   		10進数表記：821
   		16進数表記：335
   		 2進数表記：1100110101
   ----------------------------------------------------------------------------------------------------
   10456 ＋ 821 = 11277
   10456 － 821 = 9635
   10456 × 821 = 64696
   10456 ÷ 821 = 12 あまり　604
  
   821 － 10456 = 55901
  
   ----------------------------------------------------------------------------------------------------
   bit size (std::bitset size): 32
  
   Number1：
   		10進数表記：4251591574
   		16進数表記：FD6A2396
   		 2進数表記：11111101011010100010001110010110
  
   Number2：
   		10進数表記：42057761
   		16進数表記：281C021
   		 2進数表記：10100000011100000000100001
   ----------------------------------------------------------------------------------------------------
   4251591574 ＋ 42057761 = 4293649335
   4251591574 － 42057761 = 4209533813
   4251591574 × 42057761 = 1609897558
   4251591574 ÷ 42057761 = 101 あまり　3757713
  
   42057761 － 4251591574 = 85433483
  
   ----------------------------------------------------------------------------------------------------
   bit size (std::bitset size): 64
  
   Number1：
   		10進数表記：18216383274314301389
   		16進数表記：FCCD9812CDDEFFCD
   		 2進数表記：1111110011001101100110000001001011001101110111101111111111001101
  
   Number2：
   		10進数表記：274117733744976349
   		16進数表記：3CDDCA0628121DD
   		 2進数表記：1111001101110111001010000001100010100000010010000111011101
   ----------------------------------------------------------------------------------------------------
   18216383274314301389 ＋ 274117733744976349 = 43756934349726122
   18216383274314301389 － 274117733744976349 = 17942265540569325040
   18216383274314301389 × 274117733744976349 = 2286944813150978297
   18216383274314301389 ÷ 274117733744976349 = 66 あまり　124612847145862355
  
   274117733744976349 － 18216383274314301389 = 504478533140226576
  
   ----------------------------------------------------------------------------------------------------
   bit size (std::bitset size): 128
  
   Number1：
   		10進数表記：3556762637008124103711
   		16進数表記：C0CFFF45D2A2DDCC1F
   		 2進数表記：110000001100111111111111010001011101001010100010110111011100110000011111
  
   Number2：
   		10進数表記：225471468712737
   		16進数表記：CD10AACCB321
   		 2進数表記：110011010001000010101010110011001011001100100001
   ----------------------------------------------------------------------------------------------------
   3556762637008124103711 ＋ 225471468712737 = 3556762862479592816448
   3556762637008124103711 － 225471468712737 = 3556762411536655390974
   3556762637008124103711 × 225471468712737 = 801948495628809201203162767054667007
   3556762637008124103711 ÷ 225471468712737 = 15774779 あまり　47259283443588
  
   225471468712737 － 3556762637008124103711 = 340282366920938459906612195895112820482