我有类位的对象，基本上是一个类别称为值的字段，它是布尔值。
public class Bit {
private boolean value;
public Bit() {
this.value = false;
}
public Bit(boolean value) {
this.value = value;
}
public boolean getValue() {
return value;
}
}
它还有更多方法。
，然后我有一个名为号码的类，该类应该使用链接列表在其二进制表示中表示大数字，其中first -link是LSB，最后链接是MSB。例如，如果我调用构造函数数字num1 =新数字（6）;然后，我将有一个链接列表如下：0 1 1（null）
现在我想知道如何比较两个数字对象。因此，例如：如果我有num1，而数字num2 =新数字（7）;[1 1 1]然后，我想要一种方法来告诉我num2大于num1
要比较两个二进制数字，我将从MSB开始，然后比较每个位，一旦一个比另一个比较，这意味着数字更大。我可以使用bit.toint（）;
轻松地获取每个链接的整数值（bit）;因此，我正在考虑迭代列表，并一一比较钻头，问题是我的迭代符号是在first -link（LSB）之前（LSB），我知道我可以将其一直移至最终，并使用hasprevious开始迭代（）但是我没有那种方法。我想在一次仅浏览每个列表的同时这样做。有任何想法吗？
public static boolean lessEq(Number num1, Number num2){
Iterator<Bit> it1 = num1.bitIterator().;
Iterator<Bit> it2 = num2.bitIterator();
}
数字构造函数：
public Number(){
list = new LinkedList<Bit>();
list.add(new Bit(false));
}
/**
* Constructs a new Number from an int.
* @param number an int representing a decimal number
*/
public Number(int number) { // assignment #1
list = new LinkedList<Bit>();
if(number == 0) list.add(new Bit(false));
if (number < 0) throw new IllegalArgumentException("number cannot be negative");
else {
while (number > 0) {
if (number % 2 == 0) {
list.add(new Bit(false));
}else list.add(new Bit(true));
number = number / 2;
}
}
}
编辑：非常感谢您的评论！
- 最初，您假设两个数字都相等。
- 您都可以从两个数字中获得一些位。如果两者都用尽，请使用零。
- 如果两个位相等，则不会改变结果。
- 如果来自数字A的位为1，则将数字A设置为更大。
- 如果来自数字B的位为1，则将数字B设置为更大。
- 如果两个列表都用尽，请返回结果。
- 否则重复步骤2。
这考虑了您允许以不必要的零位为MSB的列表。
如果您想提交精美的家庭作业，可以从结束开始，跟踪您所处的索引，并在第一个比较时停止，而钻头不相等。
您可以做一个明显的事情：在数组中收集位，然后向后走两个阵列。或者，您可以使用递归，然后使用堆栈进行存储：
public int compareTo(Number other) {
Iterator<Bit> it1 = this.bitIterator();
Iterator<Bit> it2 = other.bitIterator();
return bitCompareTo(it1, it2);
}
private static int bitCompareTo(Iterator<Bit> it1, Iterator<Bit> it2) {
if (!it1.hasNext() && !it2.hasNext()) return 0;
boolean b1 = it1.hasNext() ? it1.next().getValue() : false;
boolean b2 = it2.hasNext() ? it2.next().getValue() : false;
int cmp = bitCompareTo(it1, it2);
if (cmp != 0) return cmp;
else return Boolean.compare(b1, b2);
}
这只能遍历每个迭代器一次，但是由于比较逻辑是递归呼叫之后的，因此您可以完成比较，因为它们会从呼叫堆栈中弹出 - 以相反的顺序，就像我们想要的那样他们。
基本上：如果我们同时到达两个迭代器的末尾，我们就不确定长度，并表示使用0，我们开始递归决策。（如果我们更快地到达一个迭代器的末端，我们假设false以零来为左填充。）在每个递归步骤中，如果我们决定（无论是长度还是更高的一对），我们只需通过决定。如果不确定较高的位，我们将尝试比较当前的位对（如果相等，Boolean.compareTo将返回0，并告诉下一个级别，我们仍未确定）。如果我们检查了所有位，但我们仍然不确定，我们只会说0现在代表"等价" - 恰恰是compareTo在这种情况下应返回的内容。
拥有compareTo后，定义其他关系运算符是微不足道的。
我认为您应该尝试一下：
public static boolean lessEq(Number num1, Number num2) {
LinkedList<Bit> bits1 = num1.list;
LinkedList<Bit> bits2 = num2.list;
if(bits1.size() == bits2.size()) {
for(int i = bits1.size() - 1; i >= 0; i++) { // reversed loop since the MSB is at the end of the list
Bit bit1 = bits1.get(i);
Bit bit2 = bits2.get(i);
if(bit1.getValue() != bit2.getValue()) {
if(bit1.getValue()){ // can be replaced with return !bit1.getValue() if you want
return false; // bit1's actual bit is true, bit2 is false, so bit1 is greater
} else {
return true;
}
}
}
return true; // all bits are the same
} else {
if(bits1.size() > bits2.size()) { // can be replaced with return bits1.size() <= bits2.size() if you want
return false; // first number has more elements, so it's greater
} else {
return true;
}
}
}
编辑
根据评论，您可以改为执行以下操作（使用迭代器）
public static boolean lessEq(Number num1, Number num2) {
Iterator<Bit> bits1 = num1.list.descendingIterator();
Iterator<Bit> bits2 = num2.list.descendingIterator();
while(bits1.hasNext() && bits2.hasNext()){
Bit bit1 = bits1.next();
Bit bit2 = bits2.next();
if(bit1.getValue() != bit2.getValue()) {
return !bit1.getValue();
}
}
return bits2.hasNext();
}
比较最少的位时没有真正的问题。您只需要跟踪到目前为止发现的差异，如果您发现高阶（更重要）位的差异，则将其丢弃。最简单的递归做到：
public class Number implements Comparable<Number> {
/** Linked list of bits, least significant bit first */
Node lsb;
public Number(int n) {
if (n < 0) {
throw new IllegalArgumentException("Negative numbers not supported, got " + n);
}
if (n == 0) {
lsb = null;
} else {
lsb = new Node(new Bit(n % 2 != 0));
n /= 2;
Node tail = lsb;
while (n > 0) {
Node newNode = new Node(new Bit(n % 2 != 0));
n /= 2;
tail.setNext(newNode);
tail = newNode;
}
}
}
@Override
public int compareTo(Number other) {
return compare(lsb, other.lsb, 0);
}
private int compare(Node left, Node right, int diffSoFar) {
if (left == null) {
if (nonZero(right)) {
return -1;
} else {
return diffSoFar;
}
}
if (right == null) {
if (nonZero(left)) {
return 1;
} else {
return diffSoFar;
}
}
int localDiff = Boolean.compare(left.getData().getValue(), right.getData().getValue());
if (localDiff != 0) {
diffSoFar = localDiff;
}
return compare(left.getNext(), right.getNext(), diffSoFar);
}
private boolean nonZero(Node list) {
if (list == null) {
return false;
}
if (list.getData().getValue()) {
return true;
}
return nonZero(list.getNext());
}
}
示例使用：
Number six = new Number(6);
Number seven = new Number(7);
System.out.println("Comparing 6 and 7: " + six.compareTo(seven));
System.out.println("Comparing 15 and 6: " + new Number(15).compareTo(six));
输出：
Comparing 6 and 7: -1 Comparing 15 and 6: 1
我假设以下Node类：
public class Node {
private Node next;
private Bit data;
// Constructor, getters, setters
}