如何有效地将基数 -2 中的正数转换为基数 - 2 中的负数？

Question

Old question name: How to effectively split a binary string in a groups of 10, 0, 11?

我有一些字符串作为输入，它们是数字的二进制表示。例如：

10011
100111
0111111
11111011101

我需要将这些字符串（或数组）分成 10、0 和 11 组，以便替换它们。

10 => 11
0 => 0
11 => 10

怎么做？我已经尝试过这些选项，但没有用。

preg_match('/([10]{2})(0{1})([11]{2})/', $S, $matches);

10011输入应该是[10][0],[11]。替换后应该是11010

UPD1.

实际上，我正在尝试做一个否定算法，将以 -2 为底的正数转换为以 -2 为底的负数。可以使用维基百科中带有循环的算法来完成。但是字节组替换要快得多。我已经实现了它，只是想优化它。

对于这种情况 0111111 可以在最后添加 0。然后将应用规则。我们可以删除结果中的前导零。输出将为 101010。

UPD2.

@Wiktor Stribiżew 提出了一个想法，即如何立即进行替换，而无需先将字节拆分为组。但我已经有了更快的解决方案。

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

这道题的意思不是做替换，而是得到一个想要的组的数组[11][0][10].

UPD3.

这是我通过转换二进制组的想法得出的解决方案。它比带循环的更快。

function solution2($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);

    $arr = str_split($S);

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

    return $arr;
}

但是@Alex Blex 答案中的解决方案更快。

Answer 1

您可以使用带有 preg_replace_callback:

的简单 /11|10/ 正则表达式

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

参见online PHP demo。

Answer 2

回答问题

algorithm for converting a positive number in a base -2 to a negative one in a base -2

我相信以下函数比正则表达式更有效：

function negate($negabin)
{
    $mask = 0xAAAAAAAAAAAAAAA;
    return decbin((($mask<<1)-($mask^bindec($negabin)))^$mask);     
}

参数是以 -2 为基数的正整数 60，例如11111011101.

该函数将参数转换为以 10 为基数，取反，然后将其转换回以-2 为基数，如 wiki 中所述：https://en.wikipedia.org/wiki/Negative_base#To_negabinary

在 64 位系统上工作，但可以很容易地在 32 位系统上工作。

如何有效地将基数 -2 中的正数转换为基数 - 2 中的负数？

How to effectively convert positive number in base -2 to a negative one in base - 2?

php

regex

binary

negation