increment a binary number without arithmetic manipulations [closed]

Input: binary string

Output: binary string that represents the binary input + 1

Example: Given 10111 as an input, output 11000

Limitations: Can't use arithmetic operators or functions (like + - * /)

Criterion: code-golf, the shortest code wins the big imaginary award.

• Related Commented Dec 17, 2020 at 15:04
• Welcome to Code Golf! To be valid, a challenge needs to have a winning criterion. This is usually code-golf, but some other ones are commonly used as well. Another problem is that Do X without Y is often problematic. Commented Dec 17, 2020 at 15:08
• Also, please use the Sandbox next time before posting a challenge, to get feedback on it.
– user
Commented Dec 17, 2020 at 15:13
• Can you clarify what counts as arithmetic operators, and what input/output methods you would allow? Commented Dec 17, 2020 at 15:21
• I assumed arithmetic operators are the usual gang of four + - * / and possibly ^ % (power and modulus) You should perhaps specify if 001 should result in 010 or if 10 is also ok. Commented Dec 17, 2020 at 15:46

s/0$/1/||s/0?(1+)$/1 .(0 x length$1)/e  Try it online! Basically: If(last digit is zero){ change it to 1} else {change the last consecutive 1's (with possibly a 0 ahead of them) with a 1 and a count of zeros that is the same number as the number of 1's matched at the end of the line. Example input lines: 00000 00001 00111 1000 1011 111 1 Example output lines: 00001 00010 01000 1001 1100 1000 10 Perl 5, 37 bytes Or one less byte with this if it's ok to not preserve leading 0's (i.e. 000110) printf"%b\n",length 1 .(1x oct"0b$_")


Try it online!

GNU sed <4.3, 49 46 44 34 30 bytes

s/.*/0&M/ # prepend 0 and append mark
: # label
s/0M/1/ # 0 incremented is 1
s/1M/M0/ # 1 incremented is 0 and the one to the left is incremented
t # if anything just changed, repeat until it doesn't (the M has disappeared)


(comments and all whitespace other that newlines are just for explanation)

This takes any amount of newline-separated binary numbers and increments each, it might give a number with leading 0s.

try it online

• Some parts of the question, such as whether there are negative numbers, were unspecified. Sed has no arithmetic, so this is guaranteed to not use them.
– Wezl
Commented Dec 17, 2020 at 15:23
• Doesn't work for repunits.
– Neil
Commented Dec 17, 2020 at 15:26
• @Neil fixed, but the question doesn't specify what to do on overflow, such as whether 11111111 is -1.
– Wezl
Commented Dec 17, 2020 at 15:29