c++ - Calculating the next higher number which has same number of set bits? -


a solution given question on geeksforgeeks website.

i wish know there exist better , simpler solution? bit complicated understand. algorithm fine.

i pretty sure algorithm efficient , easier understand linked algorithm.

the strategy here understand way make number bigger without increasing number of 1's carry 1, if carry multiple 1's must add them in.

  • given number 1001 1100

  • right shift until value odd, 0010 0111. remember number of shifts: shifts = 2;

  • right shift until value even, 0000 0100. remember number of shifts performed , bits consumed. shifts += 3; bits = 3;

  • so far, have taken 5 shifts , 3 bits algorithm carry lowest digit possible. pay back.

  • make rightmost bit 1. 0000 0101. owe 2 bits. bits -= 1

  • shift left 3 times add 0's. 0010 1000. 3 times because shifts - bits == 3 shifts -= 3

  • now owe number 2 bits , 2 shifts. shift left twice, setting leftmost bit 1 each time. 1010 0011. we've paid bits , shifts. bits -= 2; shifts -= 2; bits == 0; shifts == 0

here's few other examples... each step shown current_val, shifts_owed, bits_owed

0000 0110 0000 0110, 0, 0 # start 0000 0011, 1, 0 # shift right till odd 0000 0000, 3, 2 # shift right till 0000 0001, 3, 1 # set lsb 0000 0100, 1, 1 # shift left 0's 0000 1001, 0, 0 # shift left 1's 

0011 0011 0011 0011, 0, 0 # start 0011 0011, 0, 0 # shift right till odd 0000 1100, 2, 2 # shift right till 0000 1101, 2, 1 # set lsb 0001 1010, 1, 1 # shift left 0's 0011 0101, 0, 0 # shift left 1's 


Comments

Popular posts from this blog

twig - Using Twigbridge in a Laravel 5.1 Package -

jdbc - Not able to establish database connection in eclipse -

Kivy: Swiping (Carousel & ScreenManager) -