ビット単位
解決ビット単位で計算をするプログラムがわからないのですが。。。
たとえば、足し算なら
1010
+ 1111
------------
11001
みたく計算するプログラムを教えてください。
ビット単位も何も，普通に計算すればよいだけでは？
int x = 0x0A; // 1010(2)
int y = 0x0F; // 1111(2)
int z = x + y; // 19 : 11001(2)
つまり＋を使わずに
ビット演算子を使って結果を出したいのですが。
おもしろそうなので作ってみた。
void BitFunc( bool bDataA, bool bDataB, bool bDigitUp, bool* lpbDataC, bool* lpbNextDigitUp )
{
if( bDataA == bDataB ){ // (1, 1, bDigitUp) or (0, 0, bDigitUp)の場合
// 桁上がりの値となる
*lpbDataC = bDigitUp;
if( bDataA ){ // (1, 1, bDigitUp)の場合
// 必ず桁上がり発生
*lpbNextDigitUp = true;
}else{
*lpbNextDigitUp = false;
}
}else{ // (1, 0, bDigitUp) or (0, 1, bDigitUp)の場合
// 桁上がりと反対の値となる
*lpbDataC = !bDigitUp;
// 桁上がりがある場合、次も桁上がり
*lpbNextDigitUp = bDigitUp;
}
}
int main( void )
{
unsigned short DataA = 0x0A, DataB = 0x0F, DataC = 0x00;
bool bNextDigit = false, bBitC = false;
int iBit = 0;
for( iBit = 0; iBit < 16; iBit++ ){
// iBitの計算
BitFunc( ((DataA>>iBit) & 0x01),
((DataB>>iBit) & 0x01),
bNextDigit,
&bBitC,
&bNextDigit );
// 計算結果の反映
if( bBitC ){
DataC |= (0x01<<iBit);
}
}//for(iBit)
printf( "DataC = %X\n", DataC );
return 0;
}
む、むずかしい・・・。
こんなに複雑とは思いませんでした。
フローチャートに直したら多少わかりやすくなるかな。。。
BitFuncの中をもう少し分かりやすく？したものです。
（分かりやすくといっても、下からの桁上がりがある場合とない場合をわけているだけですが。。。）
void BitFunc( bool bDataA, bool bDataB, bool bDigitUp, bool* lpbDataC, bool* lpbNextDigitUp )
{
if( bDigitUp ){ // 桁上がり有りの場合
if( bDataA == bDataB ){ // (1,1,1) or (0,0,1)
*lpbDataC = true;
if( bDataA ){ // (1,1,1)で桁上がり有り
*lpbNextDigitUp = true;
}else{
*lpbNextDigitUp = false;
}
}else{ // (1,0,1) or (0,1,1)
*lpbDataC = false;
// 桁上がり発生
*lpbNextDigitUp = true;
}
}else{// 桁上がりなしの場合
if( bDataA == bDataB ){ // (1,1,0) or (0,0,0)
*lpbDataC = false;
if( bDataA ){ // (1,1,0)で桁上がり
*lpbNextDigitUp = true;
}else{ // (0,0,0)で桁上がりなし
*lpbNextDigitUp = false;
}
}else{ // (1,0,0) or (0,1,0)
*lpbDataC = true;
// 桁上がりなし
*lpbNextDigitUp = false;
}
}
}
わざわざありがとうございます。
これって、やっぱりフローチャートに直すとすごい複雑になるものでしょうか？
今、自分で直してるのですが、いまいちわからないもので。
このBitFunc()は筆算の考え方を応用して、特定のnビットの値に関して計算しています。
（１）加算される２つの値のそれぞれのnビットの値がbDataAとbDataBで表されています。
（２）下位の桁からの繰り上がりをbDigitUpで表しています。
（３）このbDataAとbDataBとbDigitUpの足し算を行い、この桁の値を*lpbDataCと、
繰り上がりの値*lpbNextDigitUpを求めています。
ここで、もっとも単純にすると、bDataA、bDataB、bDigitUpはそれぞれ、0か1しのいずれかなので、
組み合わせとしては2×2×2の８通りあります。
それぞのれの場合の、*lpbDataCと*lpbNextDigitUpを用意しておき、
BitFunc()の中で、その値を返すのでもOKです。
後は、main()側で一番下位のビットから順番に
（１）n番目の桁の値をBitFunc()で計算
（２）その結果をDataCに反映
（３）BitFunc()で求まった繰り上がりを次の桁の計算に利用
を桁数分（ビット数分）繰り返しています。
※一番下位の計算においては、下位桁からの繰り上がりはないので、初期値として*lpbNextDigitUpをfalse(0)にしておく。
※結果は最初に0で初期化しておくと、各桁の計算結果を“|=”で反映させることができる。
なるほど！！
完璧に理解できました！
ありがとうございました。
もう解決されたようですが、作ってみたので別解として載せてみます。
bool BitAdd(bool val1,bool val2,bool &digup){
//戻り値：計算結果
//val1,val2:左、右オペランド
//digup:[入出力]桁上がりの有無
bool val3=digup;
digup=((val1&&val2)||(val1&&val3)||(val2&&val3));
return val1^val2^val3;
}
bool Add(const void *src1,const void *src2,void *dst,unsigned int size){
//戻り値：オーバーフローの有無
//src1,src2：左、右オペランド
//dst：結果格納先
//size：src1,src2,dstの有効バイト数
unsigned char *b_src1=(unsigned char*)src1;
unsigned char *b_src2=(unsigned char*)src2;
unsigned char *b_dst=(unsigned char*)dst;
unsigned int i,j;
bool digup=false;
memset(dst,0,size);
for(i=0;i<size;i++){
for(j=0;j<8;j++){//注：1byte=8bit前提。
if(BitAdd((b_src1[i])&(0x01<<j),(b_src2[i])&(0x01<<j),digup)){
b_dst[i]|=(0x01<<j);
}
}
}
return digup;
}
int main(){
unsigned long val1=0xba987654,val2=0xfedcba98,ans;
if(Add(&val1,&val2,&ans,sizeof(unsigned long)))puts("オーバーフロー発生");
printf("ans=%x",ans);
getchar();
return 0;
}
別の視点からの方法をふと思いついたので書いてみます。
固定ビット数のみ対応、オーバーフロー検知なし、と手抜きしてますがご容赦のほどを。
考え方は後の方に書いています。
/* a+bの計算結果を返す。 */
unsigned Add(unsigned a, unsigned b)
{
while(b != 0){
unsigned next_b = (a & b) << 1;
a ^= b;
b = next_b;
}
return a;
}
/* 上関数の再帰版。効率はともかく、考え方はこちらの方がわかりやすいと思う */
unsigned RecursiveAdd(unsigned a, unsigned b)
{
if(b == 0){
return a;
}
else{
return RecursiveAdd(a ^ b, (a & b) << 1);
}
}
/* 利用サンプル */
int main()
{
unsigned val1 = 0xba987654, val2 = 0xfedcba98;
printf("%x + %x = \n", val1, val2);
printf(" %x (by Add())\n", Add(val1, val2));
printf(" %x (by RecursiveAdd())\n", RecursiveAdd(val1, val2));
printf(" %x (by '+' operator)\n", val1 + val2);
return 0;
}
考え方:
a + b == (繰り上がりを無視した足し算の結果) + (繰り上がり)
== (a ^ b) + ((a & b) << 1) （＊）
なので、
a_1 = a ^ b
b_1 = (a & b) << 1
とすれば、a + b = a_1 + b_1。
ここから、a_1とb_1にさらに式(*)を適用してa_2、b_2をつくって、さらに…… とすることができます。
このようにすると、実はb_iの下位iビットは必ず0になります(証明は省略)。
nビット数の下位nビットが0とは、単なる0ですので、最大でもn回変形を繰り返せば、0との足し算になります。
なので、b_iが0になるまで変形を繰り返し、0になったときのa_iを返せば、それがa + bの結果になります。
>(fuku 2006/03/27(月) 19:32:11)
>bool Add(const void *src1,const void *src2,void *dst,unsigned int size){
>unsigned char *b_src1=(unsigned char*)src1;
>unsigned char *b_src2=(unsigned char*)src2;
ああ・・・const消しちゃってる(汗)
以下のように訂正します・・・
const unsigned char *b_src1=(const unsigned char*)src1;
const unsigned char *b_src2=(const unsigned char*)src2;
| ツイート |  |