java - Java で 2 つの BitSet を追加する

Question

うーん、Java に 2 つの BitSet を追加する必要があります.. XOR (合計の場合) と AND (キャリーの場合) の基本演算を使用して追加を試みました..キャリーも考慮して..

しかし、答えは完全には正しくありません...これは私が試したものです..

public static BitStorage Add(int n, BitStorage ...manyBitSets)
{
    BitStorage sum = new BitStorage(0, n);      //discarding carry out of MSB
    System.out.print("Addition of: ");
    for(BitStorage bitStorage:manyBitSets)
    {
        //System.out.print(sum+"\t");
        //System.out.print(bitStorage+"\t");
        System.out.println("~~~~~");
        for(int i=n-1;i>=0;i--)
        {
            if(i==n-1)
            {
                System.out.println(sum + " + " +bitStorage);
                sum.set(i, sum.get(i)^bitStorage.get(i));
                //System.out.println(sum.get(i)+" XOR "+bitStorage.get(i));
            }
            else
            {
                System.out.println(sum + " + " +bitStorage+"\t"+(sum.get(i)?"1":"0"+"^"+(bitStorage.get(i)?"1":"0")+"^"+(sum.get(i+1)?"1":"0"+"&"+(bitStorage.get(i+1)?"1":"0"))));
                sum.set(i, sum.get(i)^bitStorage.get(i)^(sum.get(i+1)&bitStorage.get(i+1)));      //carry taken here
                //System.out.println(sum.get(i)+" XOR "+bitStorage.get(i)+" XOR ("+bitStorage.get(i+1)+" AND "+sum.get(i+1));
            }
        }
    }   
    return sum;
}

PS: BitStorage クラスは、いくつかの追加メソッドを使用した BitSet の独自の実装に他なりません.. Add、Subtract、Shift など

2 人のメンバーがいます:

1. 最大サイズとしての整数 (n) (ベクトルの拡大または縮小がビット単位の操作に影響を与えたくない => したがって、すべての操作は n に対して行われます) -> 例: n が 4 の場合、ビットは BitSet の o から 3 の位置を占めます
2. コンストラクタに渡されるサイズ n の BitSet オブジェクト

さらに 2 点:

• 私はそれを長い配列またはバイト配列に変換してから追加することを考えましたが、7ではなくJDK 6でのみソリューションが必要です
• MSB から生成されたキャリーは必要ありません。同じ no(bits)、つまり n で回答が必要です。

「欲しい...」を何度も使ってごめんなさい..ちょっと疲れました。.多くのことを試しました! そしてええと、アルゴリズムの一部としてこれが必要です..返信を楽しみにしています.. :) :)

Answer 1

疲れたので、醜いのなら許してください。あなたの持ち運び方法は完全に壊れており、何も設定すべきでない場合でも間違ったビットを設定しています。キャリーアップするためにカウントアップする必要があります。そのため、最後のビットを特別なケースにする理由はありません。キャリーは消えてしまいます。最後の結果を実際に次のループ反復に持ち込むことにより、ロジックははるかに単純になります。

public static BitStorage Add(int n, BitStorage ...manyBitSets)
{
    BitStorage sum = new BitStorage(0, n);      //discarding carry out of MSB
    System.out.print("Addition of: ");
    for(BitStorage bitStorage:manyBitSets)
    {
        boolean carry = false;
        boolean lastcarry = false;
        //System.out.print(sum+"\t");
        //System.out.print(bitStorage+"\t");
        System.out.println("~~~~~");
        for(int i=0;i<n;i++)
        {
                System.out.println(sum + " + " +bitStorage+"\t"+(sum.get(i)?"1":"0"+"^"+(bitStorage.get(i)?"1":"0")+"^"+(sum.get(i+1)?"1":"0"+"&"+(bitStorage.get(i+1)?"1":"0"))));
                lastcarry = carry;
                carry = sum.get(i) && bitStorage.get(i);
                sum.set(i, lastcarry^sum.get(i)^bitStorage.get(i));      //carry taken here
                //System.out.println(sum.get(i)+" XOR "+bitStorage.get(i)+" XOR ("+bitStorage.get(i+1)+" AND "+sum.get(i+1));
        }
    }   
    return sum;
}

変数にブール値を使用したのは、intなどを使用して変数を変更する場合に、クラスをBitSetのシンラッパーとして構築したためです。

Answer 2

さて、これは興味深い問題であり、しばらくの間推測し続けました...

最初にロジックを導出することはできませんでしたが、基本に戻りboolean expression、3ビット演算の合計とキャリーを計算するために導出しました。解決策は次のとおりです。

public static BitSet addBitSet(int n, List<BitSet> bitSetList){
    BitSet sumBitSet = new BitSet(n);
    for (BitSet firstBitSet : bitSetList) {
        BitSet secondBitSet = (BitSet) sumBitSet.clone();
        System.out.println("A:  " + printBitSet(firstBitSet, 6));
        System.out.println("B:  " + printBitSet(secondBitSet, 6));
        boolean carryForNext = false, sum,a,b,c;
        for (int i = n - 1; i >= 0; i--) {
            a=firstBitSet.get(i);
            b=secondBitSet.get(i);
            c=carryForNext;
            sum = a&!b&!c|!a&!b&c|!a&b&!c|a&b&c;
            carryForNext = a&b&!c|a&!b&c|!a&b&c|a&b&c;
            sumBitSet.set(i,sum);
        }
        System.out.println("SUM:" + printBitSet(sumBitSet, 6));
    }
    System.out.println(printBitSet(sumBitSet, 6));
    return sumBitSet;
}

そしてここにのコードがありますprintBitSet：

public static String printBitSet(BitSet bitSet, int size) {
    StringBuilder builder = new StringBuilder("");
    for (int i = 0; i < size; i++) {
        if (bitSet.get(i))
            builder.append("1");
        else
            builder.append("0");
    }
    return builder.toString();
}

Answer 3

私はバグを理解しました..それはキャリーの問題でした..代わりに同じロジックを使用します..私は別のロジックに落ち着きました..2つの数値をXORしただけです（合計を取得するために）..そして再びそれを数値の加算として扱いましたキャリーのある数値に変換します（元の数値のAND演算から取得）。LSB側のビット加算には加算するキャリーがないため、AND出力（キャリー）は反復ごとに左にシフトされます。

キャリービットセットがすべて0の場合、ループを停止します（false）

例：

1. 0001
2. +0011
3. = 0010->（XOR =合計）
4. +0010->（AND出力=キャリー..左にシフトした後に表示され、XOR出力に追加されます）
5. = 0000->（XOR =合計）
6. +0100->（AND出力=キャリー..左にシフトした後に表示され、XOR出力に追加されます）
7. = 0100->（XOR = sum .. FINAL ANSWER）
8. 0000->（AND出力=キャリー..左にシフトした後に表示されます..ここで停止します..すべてが0であるため停止します））

サンプル ：）

import java.util.*;
public class BitSetAddition
{
static String nums[] = {"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
public static void main(String args[])
{
    for(int q=0;q<nums.length;q++)
    {
        System.out.print(q+1+" -> ");
        BitSet b1 = new BitSet();
        String s = nums[q];
        b1.set(0, s.charAt(0)=='1'?true:false);
        b1.set(1, s.charAt(1)=='1'?true:false);
        b1.set(2, s.charAt(2)=='1'?true:false);
        b1.set(3, s.charAt(3)=='1'?true:false);

        for(int i=0;i<4;i++)
            System.out.print(b1.get(i)?"1":"0");
            System.out.print(" + ");

        BitSet b2 = new BitSet();
        String a = "0001";
        b2.set(0, a.charAt(0)=='1'?true:false);
        b2.set(1, a.charAt(1)=='1'?true:false);
        b2.set(2, a.charAt(2)=='1'?true:false);
        b2.set(3, a.charAt(3)=='1'?true:false);

        for(int i=0;i<4;i++)
            System.out.print(b2.get(i)?"1":"0");
            System.out.print(" = ");

        BitSet sum = new BitSet();
        BitSet carry = new BitSet();
        BitSet toAdd = new BitSet();
        BitSet tempSum = new BitSet();
        BitSet tempCarry = new BitSet();

        sum = b1;
        toAdd = b2;
        do
        {
            copy(4, tempSum, sum);
            copy(4, tempCarry, toAdd);
            tempSum.xor(toAdd);
            tempCarry.and(sum);
            copy(4, sum, tempSum);
            copy(4, carry, leftShift(4, tempCarry));
            copy(4, toAdd, carry);
            //sum.set(i, b1.get(i)^b2.get(i)^(b1.get(i+1)&b2.get(i+1)));
        }while(!carry.equals(new BitSet()));
            //if(i+2<=3)
                //sum.set(i, b1.get(i)^b2.get(i)^(b1.get(i+1)&b2.get(i+1)&(b1.get(i+2)&(b2.get(i+2)))));
            //else if(i+1<=3)
                //sum.set(i, b1.get(i)^b2.get(i)^(b1.get(i+1)&b2.get(i+1)));
            //else
                //sum.set(i, b1.get(i)^b2.get(i));
        for(int i=0;i<4;i++)
            System.out.print(sum.get(i)?"1":"0");

        System.out.println();
    }
}
static void copy(int n,BitSet b, BitSet toCopy)
{
    for(int i=0;i<n;i++)
        b.set(i, toCopy.get(i));
}
static BitSet leftShift(int n, BitSet b)
{
    for(int i=0;i<n;i++)
        b.set(i, b.get(i+1));
        b.set(n-1, false);
        return b;
}
}

プログラムのコメントは私の以前のロジックのものです..以前のロジックはもっと複雑でした：P ..必要に応じて、プログラムのコメントを無視してください:)

注：MSBビットの加算から生じるキャリーは必要ありませんでした..アルゴ（これが必要でした）によると..答え（合計）のビット数は同じです..必要に応じて誰でも調整できます:)