3v4l.org

run code in 300+ PHP versions simultaneously
<?php function reduce($bits, $prefix, $value = '0') { if (strlen($bits) == 1) { // a single bit can be flipped as needed return array($prefix . ($bits[0] == '0' ? '1' : '0')); } if ($bits[0] == $value) { // nothing to do with this bit, flip the remainder $prefix .= $bits[0]; return reduce(substr($bits, 1), $prefix); } // need to convert balance of string to 1 followed by 0's $prefix .= $bits[0]; $steps = reduce(substr($bits, 1), $prefix, '1'); // now we can flip this bit $prefix = substr($prefix, 0, -1) . ($bits[0] == '0' ? '1' : '0'); $steps[] = $prefix . str_pad('1', strlen($bits) - 1, '0'); // now reduce the new string to 0 $steps = array_merge($steps, reduce(str_pad('1', strlen($bits) - 1, '0'), $prefix)); return $steps; } foreach (array(8, 115) as $i) { $bin = decbin($i); $steps = array_merge(array($bin), reduce($bin, '')); echo "$i ($bin) takes " . (count($steps) - 1) . " steps\n"; print_r($steps); }
Output for 7.2.0 - 7.2.34, 7.3.0 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.29, 8.2.0 - 8.2.23, 8.3.0 - 8.3.11
8 (1000) takes 15 steps Array ( [0] => 1000 [1] => 1001 [2] => 1011 [3] => 1010 [4] => 1110 [5] => 1111 [6] => 1101 [7] => 1100 [8] => 0100 [9] => 0101 [10] => 0111 [11] => 0110 [12] => 0010 [13] => 0011 [14] => 0001 [15] => 0000 ) 115 (1110011) takes 93 steps Array ( [0] => 1110011 [1] => 1110010 [2] => 1110110 [3] => 1110111 [4] => 1110101 [5] => 1110100 [6] => 1111100 [7] => 1111101 [8] => 1111111 [9] => 1111110 [10] => 1111010 [11] => 1111011 [12] => 1111001 [13] => 1111000 [14] => 1101000 [15] => 1101001 [16] => 1101011 [17] => 1101010 [18] => 1101110 [19] => 1101111 [20] => 1101101 [21] => 1101100 [22] => 1100100 [23] => 1100101 [24] => 1100111 [25] => 1100110 [26] => 1100010 [27] => 1100011 [28] => 1100001 [29] => 1100000 [30] => 0100000 [31] => 0100001 [32] => 0100011 [33] => 0100010 [34] => 0100110 [35] => 0100111 [36] => 0100101 [37] => 0100100 [38] => 0101100 [39] => 0101101 [40] => 0101111 [41] => 0101110 [42] => 0101010 [43] => 0101011 [44] => 0101001 [45] => 0101000 [46] => 0111000 [47] => 0111001 [48] => 0111011 [49] => 0111010 [50] => 0111110 [51] => 0111111 [52] => 0111101 [53] => 0111100 [54] => 0110100 [55] => 0110101 [56] => 0110111 [57] => 0110110 [58] => 0110010 [59] => 0110011 [60] => 0110001 [61] => 0110000 [62] => 0010000 [63] => 0010001 [64] => 0010011 [65] => 0010010 [66] => 0010110 [67] => 0010111 [68] => 0010101 [69] => 0010100 [70] => 0011100 [71] => 0011101 [72] => 0011111 [73] => 0011110 [74] => 0011010 [75] => 0011011 [76] => 0011001 [77] => 0011000 [78] => 0001000 [79] => 0001001 [80] => 0001011 [81] => 0001010 [82] => 0001110 [83] => 0001111 [84] => 0001101 [85] => 0001100 [86] => 0000100 [87] => 0000101 [88] => 0000111 [89] => 0000110 [90] => 0000010 [91] => 0000011 [92] => 0000001 [93] => 0000000 )
preferences:
53.28 ms | 417 KiB | 5 Q