Math, asked by sainadh3003, 3 months ago

1) A binary number with n bits all of which are 1's has the value
a. n2-1
b.2n
c. 2(n-1)
d. 2n-1​

Answers

Answered by needafatima239
5

hope I have helped u!! ♥️✌

Step-by-step explanation:

Given a number x, find next number with same number of 1 bits in it’s binary representation.

For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (100012).

Algorithm:

When we observe the binary sequence from 0 to 2n – 1 (n is # of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1’s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position. An example makes it more clear,

x = 156

10

x = 10011100

(2)

10011100

00011100 - right most string of 1's in x

00000011 - right shifted pattern except left most bit ------> [A]

00010000 - isolated left most bit of right most 1's pattern

00100000 - shiftleft-ed the isolated bit by one position ------> [B]

10000000 - left part of x, excluding right most 1's pattern ------> [C]

10100000 - add B and C (OR operation) ------> [D]

10100011 - add A and D which is required number

Similar questions