Convert an integer encoded in base -2 into his negative representation with PHP

The task was to get from a positive integer encoded in the base -2 it’s negative equivalent in the same base. So, to solve this task we need to split it into two parts. In first one we will use a formula to get an integer from its code. And in the second part, we will encode this negative integer back to base -2.

For example, for number 9 it’s representation will be 1,0,0,1,1 and function should return it’s negative (-9) representation in base -2 and it will be 1,1,0,1.

Negative base or Negabinary

It would be nice to read some sources first to get a better understanding of a problem. I did it briefly while test timer was ticking and came up with the following solution.


function solution($A)
{

// if we will conver digit to a binary
//    $A = array_reverse(str_split(decbin($A)));

    $result = [];
    $N      = count($A);

    $decodedValue = 0;
    //by formula
    for ($i = $N - 1; $i >= 0; $i--) {
        $decodedValue += $A[$i] * pow(-2, $i);
    }

    $negativeDecoded = (-1) * $decodedValue;

    while ($negativeDecoded != 0) {

        $remaining = $negativeDecoded % -2;

        $negativeDecoded = intval($negativeDecoded / -2);

        if ($remaining < 0) {
            $remaining += 2;
            $negativeDecoded += 1;
        }

        $result[] = $remaining;
    }

    return $result;
}

function solution($A)

{

// if we will conver digit to a binary

// $A = array_reverse(str_split(decbin($A)));

$result = [];

$N = count($A);

$decodedValue = 0;

//by formula

for ($i = $N - 1; $i >= 0; $i--) {

$decodedValue += $A[$i] * pow(-2, $i);

}

$negativeDecoded = (-1) * $decodedValue;

while ($negativeDecoded != 0) {

$remaining = $negativeDecoded % -2;

$negativeDecoded = intval($negativeDecoded / -2);

if ($remaining < 0) {

$remaining += 2;

$negativeDecoded += 1;

}

$result[] = $remaining;

}

return $result;

}

This solution is pretty raw and made only for base -2 but it works. To understand what is going on it’s better to read these sources first:

This blog post could be perceived as introductory.
http://haacked.com/archive/2006/05/01/negativebasenumberingsystems.aspx/
Then it would lead us to Wikipedia
https://en.wikipedia.org/wiki/Negative_base
Here is more clear implementation of negative base function than presented in Wikipedia
https://gist.github.com/CMCDragonkai/841bdc56b568c9068a5d
And finally a StackOverflow question with the same problem.
http://stackoverflow.com/questions/33056593/how-to-negate-base-2-numbers

One interesting fact. I have found this question when typed B[i]*(-2)^i in google, which is a formula for representing a number in negbinary. And this formula doesn’t present on a page, there are only explanations and examples in answers. How google knows? :)

So, the first part is to convert given negbinary of a positive number into an integer with a formula – B[i]*(-2)^i.
Then using a fully described in Wikipedia process of converting an integer to negbinary we could easily get an answer.

And with this solution, I got 66% from 100%. Again. What the problem? Just imagine a very very big number with a very very long string of 0 and 1. And it’s all will be rotated through a loop. Twice.

Faster solution 1.

While working on this post I decided to search trough SO again in hope to find more information. And have found this question with an especially interesting first answer.

http://stackoverflow.com/questions/33056593/how-to-negate-base-2-numbers/33056852?noredirect=1#comment72879711_33056852

From the first try, I haven’t implemented suggested an approach negate bytes by negating groups 10 and 11 to 11 and 10 respectively. The problem was to negate a byte string which ends with 1. The answer was easy and I almost get it myself. But to be more correct I have asked the author of an answer and he answered. After that, I crafted a faster solution.


function solution2($A)
{
//    decode($A);

    $S = implode('', $A);

    //we could add leading 0
    if (substr($S, strlen($S) - 1, 1) == 1) {
        $S .= '0';
    }

    $rules = [
        '10' => '11',
        '0'  => '0',
        '11' => '10',
    ];

    $S = strtr($S, $rules);

//    $S = preg_replace_callback("/11|10/", function($m) {
//        return $m[0] == "11" ? "10" : "11"; // if 11 is matched, replace with 10 or vice versa
//    }, $S);

    $arr = str_split($S);

    while ($arr[count($arr) - 1] == 0) {
        array_pop($arr);
    }

    return $arr;
}

function solution2($A)

{

// decode($A);

$S = implode('', $A);

//we could add leading 0

if (substr($S, strlen($S) - 1, 1) == 1) {

$S .= '0';

}

$rules = [

'10' => '11',

'0' => '0',

'11' => '10',

];

$S = strtr($S, $rules);

// $S = preg_replace_callback("/11|10/", function($m) {

// return $m[0] == "11" ? "10" : "11"; // if 11 is matched, replace with 10 or vice versa

// }, $S);

$arr = str_split($S);

while ($arr[count($arr) - 1] == 0) {

array_pop($arr);

}

return $arr;

}

Commented out code is a slower way to do the same replacement. But while thinking about this solution I also was wondering how faster it would be to have a way to get all groups for replacement, replace them and then just implode them back into a string. And I even created a question on a SO for this reason. But as an answer, I got something even more interesting.

http://stackoverflow.com/questions/42951205/how-to-effectively-convert-positive-number-in-base-2-to-a-negative-one-in-base/

From Wikipedia, I have missed an approach with a byte mask. The problem is that suggested to a negabinary algorithm and to negative base algorithms were produce different results. Or to a negabinary algorithm implemented in PHP works in a different way. I’m not sure. So, I managed to fix this solution using decode() function from fist solution first and then using a mask.


function solution3($A)
{
    //64 bit
    $mask = 0xAAAAAAAAAAAAAAA;
    //32 bit
//    $mask = 0xAAAAAAAA;

    $value = decode($A);

    $opResult = (-$value + $mask) ^ $mask;
    $result   = decbin($opResult);

//    $S = implode('', $A);
//    $opResult = (($mask << 1) - ($mask ^ bindec($S))) ^ $mask;
//    $result = decbin($opResult);

    return array_reverse(str_split($result));
}

function solution3($A)

{

//64 bit

$mask = 0xAAAAAAAAAAAAAAA;

//32 bit

// $mask = 0xAAAAAAAA;

$value = decode($A);

$opResult = (-$value + $mask) ^ $mask;

$result = decbin($opResult);

// $S = implode('', $A);

// $opResult = (($mask << 1) - ($mask ^ bindec($S))) ^ $mask;

// $result = decbin($opResult);

return array_reverse(str_split($result));

}

Commented out code is not working suggestion from SO answer.

With this code, I have the same output as with solution1 and 2 code. But solution 2 is much faster because we avoid here using decode() function with a loop through every digit in a binary string. And I don’t know a different way to decode binary -2 into a digit more effectively. Solution2 is the absolute winner here with direct conversion of binary groups.

The test results on an 800 character length binary string are:

Solution1 and 3 – 0.0005 seconds
Solution 2 – 0.0001 seconds

UPD. after 15-20 minutes.

I have figured out, that 9 in a base -2 is 11001 and 15 is 10011. It means that I have reversed binary string as input. :) But it’s not a mistake, it was provided by my task definition.
Then I have fixed a solution proposed in SO answer to my question and it’s work.


function solution4($A)
{
    $mask = 0xAAAAAAAAAAAAAAA;

    $S        = implode('', array_reverse($A));
    $opResult = (($mask << 1) - ($mask ^ bindec($S))) ^ $mask;
    $result   = decbin($opResult);

    return array_reverse(str_split($result));
}

function solution4($A)

{

$mask = 0xAAAAAAAAAAAAAAA;

$S = implode('', array_reverse($A));

$opResult = (($mask << 1) - ($mask ^ bindec($S))) ^ $mask;

$result = decbin($opResult);

return array_reverse(str_split($result));

}

Now, solution4 is an absolute winner. Tests results:

Solution 2 – 0.0001 seconds
Solution 4 – 0.0000 seconds.

Why all zeros? It means that it needs more deep precision to reach first digit greater than zero. Or bigger digit should be used as an input. We could conclude that solution4 with a mask at least 10 times faster that solution2 with groups replacing.

Cosmonaut in a boat

Personal blog of Oleg Abrazhaev about programming, technologies and life

Convert an integer encoded in base -2 into his negative representation with PHP

Negative base or Negabinary

Negative base or Negabinary

Похожие посты: