6

Quick Background for this.

I am writing a Site.com page to gather client Data for configuring of routers. I currently ask users to enter there internal IP Address and Submask.

I then work out the IP Ranger. I believe to do this requires Binary Conversations and Addition.

IP Inputs

I have everything working well apart from the Binary Addition. I have written a full adder and half adder however my results come out as "011111111111111111111111111111111"

can anyone see what i've done wrong?

PS, All Conversation are working correctly to get the first Available Address. It is the LAST address I am having an issue with.

private static String binaryAddition(List<String> aInput, List<String> bInput)
    {
        String a = '';
        for(String s : aInput)
            a = a + s;
    String b = '';
    for(String s : bInput)
        b = b + s;

    String sum = '';
    String carry = '';

    for(Integer i = a.length() -1; i>=0; i-- )
    {
        if( i == a.length() - 1)
        {
            Adder halfAdd1 = halfAdder(a.substring(i, i+1),b.substring(i, i+1)); 
            sum = halfAdd1.sum + sum;
            carry = halfAdd1.carry; 
        }
        else
        {
            Adder fullAdd = fullAdder(a.substring(i, i+1),b.substring(i, i+1), carry);
            sum = fullAdd.sum+sum;
            carry = fullAdd.carry;
        }

    }

    return (carry.equals('0') ? carry + sum : sum );
}

private static Adder fullAdder(String a, String b, String carry)
{   
    Adder halfAdd = halfAdder(a,b);

    string sum = xorOp(carry, halfAdd.sum);
    carry = andOp(carry, halfAdd.sum);
    //carry += orOp(carry, halfAdd.carry);

    Adder result = new Adder();
    result.sum = sum;
    result.carry = carry;
    return result;
}

private static Adder halfAdder(String a, String b)
{
    string sum = xorOp(a,b);
    string carry = andOp(a,b);


    Adder result = new Adder();
    result.sum = sum;
    result.carry = carry;
    return result;
}

private static String xorOp(String a, String b)
{
    return (a == b ? '0' : '1');
}

private static String andOp (String a, String b)
{
    return a == '1' && b == '1' ? '1' : '0';
}

private static String orOp(String a, String b)
{
    return a;
}

public class Adder
    {
        String sum;
        String carry;
    }

3 Answers 3

3

Breaking down an IPv4 address (and the netmask) to a binary string, implementing 1-bit adders, and then converting back to an IPv4 address seems to me to be doing things the hard way.

Granted, there really isn't an 'easy' way to go about manipulating IP addresses, but the route that I chose to go down when I implemented a set of IP Address utility methods (it was one of my first big projects as a professional developer, when script statement limits in Apex were still a thing) was to work in integers as much as possible.

I might go about it slightly differently if I were to re-implement things today, but the starting point I used was to convert an IPv4 address, represented in dot-decimal notation as a string, to a List<Integer>.

That bit is simple enough.

// Assume ipString is declared elsewhere, and is of the form '192.168.0.0'
// split takes a regexp, so to split on the period/full-stop literal, we need to escape.
// Working in apex, we also need to escape the backslash.
List<String> stringOctets = ipString.split('\\.')

List<Integer> octets = new List<Integer>();
for(String octet :stringOctets){
    octets.add(Integer.valueOf(octet));
}

// octets contains [192, 168, 0, 0]

Once both the given IPv4 address and the netmask are integer lists, getting the first address in the range is as simple as stepping through each octet (of both the IPv4 address, and the netmask), and performing a bitwise-and.

// Assume that netmask and ipAddress are both List<Integer>s
List<Integer> firstAddressInRange = new List<Integer>();

for(Integer i = 0; i < netmask.size(); i++){
    // A single ampersand (&) is the bitwise-and operator
    firstAddressInRange.add(netmask[i] & ipAddress[i]);
}

The last address in a range is a bit trickier. It's the bitwise-or of the given ip address together with the inverse of the netmask. There isn't a bitwise-not that I'm aware of, so we'll need to implement invert() ourselves. Luckily, it's easy enough.

// Since we can't say that we want to use an 8-bit unsigned integer, we'll
//   need to do a little bit of work to ensure that every bit after the 8 least-significant
//   bits are 0.
// If we don't, we risk things going horribly wrong in other bitwise operations
private static Integer invert(Integer original){
    // 255 - original gives us the inverse
    // bitwise-and with 255 ensures that everything beyond the first 8 bits is 0
    return 255 & (255 - original);
}

Now that we have our invert() method, we can find the last address in a range

// Assume that netmask and ipAddress are both List<Integer>s
List<Integer> lastAddressInRange = new List<Integer>();

for(Integer i = 0; i < netmask.size(); i++){
    // A single pipe (|) is the bitwise-or operator
    lastAddressInRange.add(invert(netmask[i]) | ipAddress[i]);
}

From here, you could add handling for IPv6 without too much trouble. The algorithms for finding the first and last addresses in the range remain the same. The invert method would simply need to have 255 replaced with 65535. The biggest pain, really, would be that you need to convert from hexadecimal to decimal (and then back again when you wanted to display the resulting IPv6 address).

If you need anything other than the first and last addresses in a range, then implementing add() and subtract() methods would be helpful. I won't provide an implementation of those (unless asked), but the algorithm is simple enough.

  • Add the number passed to 'add()' to the last octet
  • Iterate over the octets in reverse (i.e. if the IP address is 192.168.0.1, start with the '1' octet)
    • Perform integer division to see how much needs to be added to the next octet
    • Set current octet's value to (current octet % 256)

Subtracting is nothing more than adding a negative, but you'd need to change the logic a bit to support borrowing from greater octets.

1
  • Thank you, This is a great response and has been a great help. Mar 9, 2017 at 21:32
0

I think you need to be using one of the bitwise operators for the carry either |, ^, or ^=. You could also use a bitwise shift operator like >>, <<, or >>> as appropriate. See Understanding Expression Operators in the Apex Docs for more on their use.

0

Doing binary operations on strings seems like a rather painful way to go about this.

Putting that aside for a moment, the fullAdder() method you've provided is where your problems are coming from (your implementation isn't correct). More specifically, your fullAdder's sum is correct, but the carry-out from your fullAdder is not.

There are plenty of images and descriptions of how to implement a full-adder using half-adders (and an 'OR'), so I won't go into how that works. A correct fullAdder() method, reusing the half-adder implementation you already have, would look like this

private static Adder fullAdder(String a, String b, String carryIn)
{   
    Adder halfAdd = halfAdder(a,b);

    Adder otherHalfAdd = halfAdder(halfAdd.sum, carryIn);

    Adder result = new Adder();
    result.sum = otherHalfAdd.sum;
    result.carry = orOp(halfAdd.carry, otherHalfAdd.carry);
    return result;
}

Additionally, your orOp() method is currently not correctly implemented. I'll leave fixing that implementation to you (since it should be almost exactly the same as your andOp() implementation).

That should get your solution working, but again, using strings as a binary representation seems like the long, hard, and painful way to go about this. Rethinking your approach would be an entirely separate answer (which I'll now start on writing).

+edit:

I'm not exactly sure how binary addition is involved in finding the last IP address in a subnet. This answer should get your full adder to work, but if people can't work out how you'd use this to arrive at the last IP address in a subnet, I'd take that as a red flag that your current approach isn't a great one.

In a way, this seems like a bit of an X-Y problem. You have a problem X (finding the last IP address in a subnet), and are asking about the solution, Y, that you've decided upon (using a full adder) instead of asking how to accomplish X.

If that's the case, then my other answer is the far better one even if you want to continue using a binary string to represent IP addresses and netmasks (internal to your application, at least).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.