0

嗯，我需要在java中添加两个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点：

  • 我想将它转换为长数组或字节数组，然后添加，但我只需要 JDK 6 而不是 7 中的解决方案
  • 我不需要从 MSB 生成的进位，我想要相同的 no(bits) 的答案，即 n

很抱歉多次使用“我想要……”……有点累。.尝试了很多东西！嗯，我需要这个作为算法的一部分..期待回复.. :) :)

4

3 回答 3

2

我累了，如果它很丑，请原谅我。你的携带方法完全被破坏了并且设置了错误的位，即使它不应该设置任何东西。您应该向上计数，因此，没有理由对最后一位进行特殊处理，进位就会消失。通过实际将最后一个结果带到下一个循环迭代中，逻辑要简单得多。

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;
}

我对变量使用布尔值，因为我将类构建为 BitSet 上的瘦包装器，如果您使用 int 或其他任何东西而不是更改它们。

于 2012-07-29T07:12:42.620 回答
1

嗯，这是一个有趣的问题，让我猜测了一段时间......

我无法先推导出逻辑，但随后我切换回基础知识并推导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();
}
于 2012-07-29T08:00:08.880 回答
0

我发现了这个错误..这是进位的问题..而不是使用相同的逻辑..我选择了另一个逻辑..只是对两个数字进行异或（得到总和）..并再次将其视为一个数字相加它到一个具有进位的数字（从原始数字与运算中获得）.. AND 输出（进位）在每次迭代中左移.. 因为 LSB 侧位加法没有任何要添加的进位

当进位位集全为 0（假）时，我们停止循环

一个例子：

  1. 0001
  2. +0011
  3. =0010 -->（异或=总和）
  4. +0010 -->（AND输出=进位..左移后显示，现在将添加到XOR输出）
  5. =0000 -->（异或=总和）
  6. +0100 -->（AND输出=进位..左移后显示，现在将添加到XOR输出）
  7. =0100 -->(XOR = sum ..最终答案)
  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 位加法产生的进位 .. 根据算法（我需要这个）.. 所以答案（总和）具有相同的位数.. 任何人都可以根据需要进行调整:)

于 2012-07-29T12:36:11.980 回答