Object oriented programming comparing linkedlists

Question

I have objects of class Bit which is basically a class that has one field called value and it's boolean.

public class Bit {

    private boolean value;

    public Bit() {
        this.value = false;
    }

    public Bit(boolean value) {
        this.value = value;
    }

    public boolean getValue() {
        return value;
    }
}

and it has some more methods.

and then I have a class called number which is supposed to represent large number in their binary representation using a linked list where the firstlink is the LSB and the lastlink is the MSB. for instance if I call the constructor Number num1 = new Number(6); then I'll have a linked list like the following : 0 1 1 (null)

Now I wanna know how to be able to compare two Number objects. so for example: if I have num1, and Number num2 = new Number (7); [ 1 1 1 ] then I want a method to tell me that num2 is larger than num1

to compare two binary numbers simply I would start with the MSB and compare each bit and once one is larger than the other that means the number is larger. I could easily get the integer value of each Link(Bit) using Bit.toInt();

So I was thinking of iterating over the list and comparing the bits one by one , problem is that my iterator stars before firstlink (LSB) , I know I could move it all the way to the end and start iterating using hasPrevious() but I don't have that method. I wanna be able to do that while only going over each list once. Any ideas?

public static boolean lessEq(Number num1, Number num2){ 
    Iterator<Bit> it1 = num1.bitIterator().;
    Iterator<Bit> it2 = num2.bitIterator();
}

Number constructors:

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

Edit: it Works Thanks very much for the comments !

Answer 1

I think you should try this:

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

EDIT

According to comments you can do the following instead (using iterators)

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

Answer 2

You can do an obvious thing: collect the bits in an array, then walk the two arrays backwards. Or, you can use recursion, and use the stack for storage:

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

This traverses each iterator only once, but since the comparison logic is after the recursive call, you get the comparisons done as they are popped off the call stack - in reverse order, just like we want them.

Basically: If we reach the end of both iterators at the same time, we're undecided on length alone, and signal that with 0, and we kick off our recursive decision-making. (If we reach the end of one iterator sooner, we assume false to left-pad that number with zeroes.) In each recursive step, if we've decided (whether on length or on a higher bit pair), we just pass that decision along. If the higher bits were undecided, we try to compare the current bit pair (and if it's equal, Boolean.compareTo will return 0, telling the next level down that we're still undecided). If we inspected all bits and we're still undecided, we'll just say 0 now stands for "equal" - precisely what compareTo should return in that case.

Once you have compareTo, it is trivial to define the other relational operators.

Answer 3

1. Initially you assume that both numbers are equal.
2. You get bits from both numbers. Use zero if either was exhausted.
3. If both bits are equal, you don't alter the result.
4. If bit from number A is 1, then set number A to be larger.
5. If bit from number B is 1, then set number B to be larger.
6. If both lists are exhausted, return result.
7. Otherwise repeat from step 2.

This takes into account the case where you allow lists with unnecessary zero bits as MSB.

If you want to submit fancy homework you can start from the end, keep track of the index you're at and stop at the first comparison where the bits are not equal.

Answer 4

There’s no real problem in comparing from the least significant bit. You just need to keep track of the difference found so far, and discard it if you find a difference on a higher-order (more significant) bit. It’s easiest to do it recursively:

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

Example use:

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

Output:

Comparing 6 and 7: -1
Comparing 15 and 6: 1

I am assuming the following Node class:

public class Node {
    private Node next;
    private Bit data;
    // Constructor, getters, setters
}