32ビット環境で64ビット整数を扱う (加法編) (Codelogy)

32ビット環境で64ビット整数を扱う (加法編)

通常用いられる整数型 (32ビット符号付き) は -2,147,483,648 ～ 2,147,483,647 の範囲の値を表現することができます。
殆どのアプリケーションにおいては、この制限が問題になることはまずありません。
しかし、この範囲を超える値を扱う必要のあるアプリケーションも存在します。

そこで考え付くのが、32ビット環境で64ビット整数を扱うための仕組みを作ることですが、実際にやってみると意外なほどに手間が掛ってしまいます。
この記事では、四則演算・10進出力などのプログラムを組むときの手順や考え方について解説していきます。

64ビット整数の表現

まず、64ビット整数を表現するための構造体を定義します。
DWORD (unsigned long) 組み込みの整数型は最大で32ビットまでなので、これを 2つ組み合わせて64ビット整数を表現します。

#ifndef __QWORD_H__
#define __QWORD_H__

//32ビット整数
typedef unsigned long DWORD;

//64ビット整数
typedef struct {
    DWORD dwLow;  //下位32ビット
    DWORD dwHigh; //上位32ビット
} QWORD;

#undef //__QWORD_H__
//[EOF]

メンバ dwHigh の最上位ビットは符号ビットとして利用しますが、この段階では特に気にする必要はないでしょう。

32ビット値の加算と繰り上がり

2つの QWORD 値の和を直接計算することはできないので、これらのオブジェクトのメンバ dwLow, dwHigh を個別に足し合わせ、その結果を組み合わせてこれを求めることにしましょう。演算結果の下位32ビットは dwLow の和に等しいので、これは簡単に求められます。一方、演算結果の上位32ビットの値を求めるには、dwHigh の和に下位32ビットの加算からの「繰り上がり (carry)」を加える必要があります。

しかし、DWORD (32ビット) 値を単純に + 演算子を用いて加算したのでは、この繰り上がりの値を得ることができません。そこで、DWORD の加算を、繰り上がりの計算まで含めて行うこのとのできる関数 add32 を以下のように定義します。

#define NULL 0

//略記用マクロ
#define LOWORD(dw) (0xFFFFUL & dw)
#define HIWORD(dw) (0xFFFFUL & (dw >> 16);

//32ビット整数の加算
DWORD add32(DWORD dw1, DWORD dw2, DWORD* lpdwCarry =NULL){

    DWORD dwTmp1 =LOWORD(dw1) + LOWORD(dw2);
    DWORD dwTmp2 =HIWORD(dw1) + HIWORD(dw2) + HIWORD(dwTmp1);

    DWORD dwSum   =LOWORD(dwTmp1) | (dwTmp2 << 16))
    DWORD dwCarry =HIWORD(dwTmp2);

    //繰り上がりの格納
    if (lpdwCarry) *lpdwCarry =dwCarry;

    return dwSum;
}

【図1: 関数 add32 の動作】

この関数は、繰り上がりの値を得るために、DWORD を上位16, 下位16ビットに分けて加算を行います。(図1)
和は戻り値として返され、繰り上がりの値は lpdwCarry で指定された変数に格納されます。

64ビット値の加算

前節で作成した関数 add32 を使用して、QWORD (32ビット) の加算を行う関数add を以下のように定義します。

//64ビット整数の加算
QWORD add(QWORD qw1, QWORD qw2){

    DWORD dwCarry;

    QWORD qwSum;
    qwSum.dwLow  =add32(qw1.dwLow, qw2.dwLow, &dwCarry);
    qwSum.dwHigh =add32(add32(qw1.dwHigh, qw2.dwHigh), dwCarry);

    return dwSum;
}

下位32ビット (dwLow) の加算で生じた繰り上がりを dwCarry に格納し、これを上位32ビット (dwHigh) の和に加えたものを、演算結果 dwSum の上位32ビットとしています。

#include <stdio.h>

int main(){

    QWORD qw1;
    qw1.dwLow  =0xFFFFFFFF;
    qw1.dwHigh  =0x00000007;

    QWORD qw2;
    qw2.dwLow  =0xB;
    qw2.dwHigh =0x8;

    QWORD qwSum =add(qw1, qw2);

    printf("qwSum.dwLow  => %08X\n", qwSum.dwLow);
    printf("qwSum.dwHigh => %08X\n", qwSum.dwHigh);

    return 0;
}

qwSum.dwLow  => 0000000A
qwSum.dwHigh => 00000010

きちんと加算が行われていることを確認して頂けたでしょうか？
次の記事では、減法を行う方法について解説する予定です。

追記

~~暇人プロ学生~~篤志家の nsdt さんが読みやすい図を作ってくれたよ！
　ﾊ_ﾊ
('(ﾟ∀ﾟ∩　ありがと！
　ヽ　　〈
　　ヽヽ_)

担当: 成田 (図を描くのが大変)

日時: 2008年09月04日 19:00 | パーマリンク