Введение
В информатике и математике, проблема Иосифа (или перестановка Иосифа) — это теоретическая задача, связанная с определённой игрой с выбыванием. Такие игры используются для выбора человека из группы, например, игра «эни, мини, майни, мо». [[Файл:JosephusProblemDrawing.png|thumb|right|Иллюстрация последовательности решения задачи Иосифа для 500 человек с шагом выбывания 6. Горизонтальная ось — номер человека. Вертикальная ось (сверху вниз) — время (номер цикла). Живой человек изображён зелёным цветом, выбывший — чёрным. Но сохранившийся славянский манускрипт Иосифа рассказывает другую историю: он «хитро подсчитывал номера и таким образом сумел обмануть всех остальных». У Иосифа был сообщник; задача заключалась в том, чтобы определить места двух последних выживших (чей сговор обеспечил бы их спасение). Утверждается, что он поместил себя и другого человека на 31-е и 16-е места соответственно (для k = 3, указанного ниже).
In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting out game. Such games are used to pick out a person from a group, e. g. eeny, meeny, miny, moe. [[File:JosephusProblemDrawing. png|thumb|right|A drawing for the Josephus problem sequence for 500 people and skipping value of 6. The horizontal axis is the number of the person. The vertical axis (top to bottom) is time (the number of cycle). A live person is drawn as green, a dead one is drawn as black. But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”. Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for k = 3 below).
Решение
thumb|link=|Предпоследнее (розовое) и конечное (ультрамариновое) места в задаче Иосифа для различных размеров группы, n, и шага, k. В [SVG-файле] наведите курсор на значения, чтобы увидеть полный порядок устранения. Далее, обозначает количество людей в исходном круге, а – счетчик для каждого шага, то есть, людей пропускают, и -й человек исключается. Люди в круге пронумерованы от до , начальная позиция – , а счет ведется включительно.
Битовый
Самый простой способ найти безопасную позицию — использовать побитовые операторы. В этом подходе сдвиг самого старшего установленного бита числа n в самый младший бит вернет безопасную позицию.