text: Josephus Problem Using Bit Magic | C program for josephus problem ; function to find the position of the Most Significant Bit ; keeps shifting bits to the right until we are left with 0 ; function to return at which place Josephus should sit to avoid being killed ; Getting the position of the Most Significant Bit ( MSB ) . The leftmost '1' . If the number is '41' then its binary is '101001' . So msbPos ( 41 ) = 6 ; ' j ' stores the number with which to XOR the number ' n ' . Since we need '100000' We will do 1 << 6 - 1 to get '100000' ; Toggling the Most Significant Bit . Changing the leftmost '1' to '0' . 101001 ^ 100000 = 001001 ( 9 ) ; Left - shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 ( 18 ) ; Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place . 010010 | 1 = 010011 ( 19 ) ; hard coded driver main function to run the program
code: #include <stdio.h> NEW_LINE int msbPos ( int n ) { int pos = 0 ; while ( n != 0 ) { pos ++ ; n = n >> 1 ; } return pos ; } int josephify ( int n ) { int position = msbPos ( n ) ; int j = 1 << ( position - 1 ) ; n = n ^ j ; n = n << 1 ; n = n | 1 ; return n ; } int main ( ) { int n = 41 ; printf ( " % d STRNEWLINE " , josephify ( n ) ) ; return 0 ; }