The Gateway to Computer Science Excellence

+2 votes

Best answer

First, let's see some inputs and their corresponding outputs to get an idea of what we want to build.

Input | Output |
---|---|

100110 | 100101 |

111111 | 111110 |

001001 | 001000 |

110000 | 101111 |

Things to note here:

Starting from the LSB of the input, we change every **0** we see to a** 1**, and on encountering the first **1,** we change it to a **0**. Then the remaining bits remain the same.

e.g. when the input is **10100**, we get the output 10011(subtracting 1 from the input). The 0 at the LSB is turned to a 1, then the next 0 is also turned to a 1, then on the first 1 (from LSB side), we change it to a 0. The remaining bits (up till MSB) remain the same.

This gave me the idea for the machine:

Here **state q1 flips all the bits until we get a 1. On a 1 we move to state q2, where all the inputs bits remain the same.**

NOTE: The input is provided to the machine from the least significant bit. i.e., scanning of the input is from left to right.

P.S. All all 0 input, the machine will give all 1s.

0 votes

I will encourage you to solve the problem and its quite interesting, nevertheless, I will provide you the hints just to help you out in decoding the logic.

decrementing 1 from a binary number is equivalent to adding it's 2's complement to it.

Let's take an example:

Let a 4-bit binary number, A=0111 (+7),

add 4-bit -1 to it, lets call it B=1111(-1)

A+B=0110,

Notice is LSB is 1, its directly switched to 0.

Decreasing the result further by 1, we get +5, as, 0101.

So if LSB is 0, and second bit from Left is 1, make it 0 and Leftmost bit as 1.

Generalizing it, if k bits from left are 0 and k+1th is 1 then make all the k bits 1 and k+1th bit will become 0 from 1.

Extrapolate the result on various examples and ones you understand the logic, try to design the machine by your own.

decrementing 1 from a binary number is equivalent to adding it's 2's complement to it.

Let's take an example:

Let a 4-bit binary number, A=0111 (+7),

add 4-bit -1 to it, lets call it B=1111(-1)

A+B=0110,

Notice is LSB is 1, its directly switched to 0.

Decreasing the result further by 1, we get +5, as, 0101.

So if LSB is 0, and second bit from Left is 1, make it 0 and Leftmost bit as 1.

Generalizing it, if k bits from left are 0 and k+1th is 1 then make all the k bits 1 and k+1th bit will become 0 from 1.

Extrapolate the result on various examples and ones you understand the logic, try to design the machine by your own.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,406 comments

105,170 users