Я видел, как этот вопрос задавали много, но никогда не видел истинного конкретного ответа на него. Итак, я собираюсь опубликовать один здесь, который, надеюсь, поможет людям понять, почему именно происходит «смещение по модулю» при использовании генератора случайных чисел, как rand()в C ++.

Так rand()же как и генератор псевдослучайных чисел, который выбирает натуральное число между 0 и RAND_MAXявляется константой, определенной в cstdlib(см. Эту статью для общего обзораrand() ).

Что произойдет, если вы захотите сгенерировать случайное число, скажем, между 0 и 2? Для объяснения, скажем RAND_MAX, 10, и я решил сгенерировать случайное число от 0 до 2, позвонив rand()%3. Тем rand()%3не менее, не производит числа между 0 и 2 с равной вероятностью!

Когда rand()возвращается 0, 3, 6, или 9, rand()%3 == 0 . Следовательно, P (0) = 4/11

Когда rand()возвращается 1, 4, 7 или 10 rand()%3 == 1 ,. Следовательно, P (1) = 4/11

Когда rand()возвращается 2, 5 или 8 rand()%3 == 2 ,. Следовательно, P (2) = 3/11

Это не генерирует числа между 0 и 2 с равной вероятностью. Конечно, для небольших диапазонов это может быть не самой большой проблемой, но для большего диапазона это может исказить распределение, смещая меньшие числа.

Так когда же rand()%nвозвращается диапазон чисел от 0 до n-1 с равной вероятностью? Когда RAND_MAX%n == n - 1. В этом случае, наряду с нашим более ранним предположением rand(), возвращает число между 0 и RAND_MAXс равной вероятностью, классы по модулю n также будут равномерно распределены.

Итак, как мы решаем эту проблему? Грубо говоря, продолжать генерировать случайные числа, пока вы не получите число в нужном диапазоне:

int x; 
do {
    x = rand();
} while (x >= n);

но это неэффективно для низких значений n, поскольку у вас есть только n/RAND_MAXшанс получить значение в вашем диапазоне, и поэтому вам нужно будет выполнять RAND_MAX/nвызовы в rand()среднем.

Более эффективный подход на основе формул состоял бы в том, чтобы взять некоторый большой диапазон с длиной, кратной n, например RAND_MAX - RAND_MAX % n, продолжать генерировать случайные числа до тех пор, пока вы не получите значение, лежащее в диапазоне, а затем взять модуль:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

Для небольших значений nэто редко потребует более одного вызова rand().

Работы цитируются и читаем дальше:

• CPlusPlus Ссылка

• Вечно Смущенный

Продолжайте выбирать случайное число - это хороший способ убрать смещение.

Обновить

Мы могли бы сделать код быстрым, если бы мы искали x в диапазоне, кратном n.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

Вышеуказанный цикл должен быть очень быстрым, скажем, в среднем за 1 итерацию.

@ user1413793 правильно о проблеме. Я не буду обсуждать это дальше, за исключением одного замечания: да, для малых значений nи больших значений RAND_MAXсмещение по модулю может быть очень маленьким. Но использование шаблона смещения означает, что вы должны учитывать смещение каждый раз, когда вычисляете случайное число и выбираете разные шаблоны для разных случаев. И если вы сделаете неправильный выбор, ошибки, которые он вносит, неуловимы и почти невозможны для модульного тестирования. По сравнению с использованием только соответствующего инструмента (такого как arc4random_uniform), это дополнительная работа, а не меньшая. Выполнение большей работы и получение худшего решения - это ужасная разработка, особенно если делать это правильно каждый раз легко на большинстве платформ.

К сожалению, реализации решения все неверны или менее эффективны, чем должны быть. (Каждое решение имеет различные комментарии, объясняющие проблемы, но ни одно из решений не было исправлено для их решения.) Это может сбить с толку случайного ищущего ответа, поэтому я предоставляю здесь заведомо хорошую реализацию.

Опять же, лучшее решение - это просто использовать arc4random_uniformна платформах, которые его предоставляют, или аналогичное решение для вашей платформы (например, Random.nextIntна Java). Он будет делать правильные вещи без затрат на код. Это почти всегда правильный звонок.

Если у вас его нет arc4random_uniform, то вы можете использовать возможности open source, чтобы точно увидеть, как он реализован поверх более широкого диапазона ГСЧ ( ar4randomв данном случае, но аналогичный подход может также работать поверх других ГСЧ).

Вот реализация OpenBSD :

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Стоит отметить последний комментарий коммита по этому коду для тех, кому нужно реализовать похожие вещи:

Измените arc4random_uniform () для вычисления 2**32 % upper_boundкак -upper_bound % upper_bound. Упрощает код и делает его одинаковым на архитектурах ILP32 и LP64, а также немного быстрее на архитектурах LP64, используя 32-разрядный остаток вместо 64-разрядного остатка.

Указано Джорденом Вервером на tech @ ok deraadt; нет возражений от диджей или отто

Реализация Java также легко доступна (см. Предыдущую ссылку):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }

Определение

Смещение по модулю является внутренним смещением при использовании арифметики по модулю, чтобы уменьшить выходной набор до подмножества входного набора. В общем случае, смещение существует всякий раз, когда отображение между входным и выходным набором распределяется неравномерно, как в случае использования арифметики по модулю, когда размер выходного набора не является делителем размера входного набора.

Этого смещения особенно трудно избежать в вычислениях, где числа представлены в виде цепочек битов: 0 и 1. Найти действительно случайные источники случайности также чрезвычайно сложно, но это выходит за рамки этого обсуждения. В оставшейся части этого ответа предположим, что существует неограниченный источник действительно случайных битов.

Пример задачи

Давайте рассмотрим моделирование броска кубика (от 0 до 5) с использованием этих случайных битов. Есть 6 возможностей, поэтому нам нужно достаточно бит для представления числа 6, которое составляет 3 бита. К сожалению, 3 случайных бита дают 8 возможных результатов:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Мы можем уменьшить размер набора результатов ровно до 6, взяв значение по модулю 6, однако это представляет проблему смещения по модулю : 110дает 0 и 1111. Этот кубик загружается.

Потенциальные решения

Подход 0:

Вместо того, чтобы полагаться на случайные биты, теоретически можно нанять небольшую армию, чтобы бросать кости весь день и записывать результаты в базу данных, а затем использовать каждый результат только один раз. Это примерно так же практично, как кажется, и, скорее всего, не даст действительно случайных результатов в любом случае (каламбур).

Подход 1:

Вместо того чтобы использовать модуль, наивный , но математически правильное решение , чтобы отменить результаты , что выход 110и 111и просто попробовать еще раз с 3 - мя новыми битами. К сожалению, это означает, что есть на каждый бросок с вероятностью 25% потребуется повторный бросок, включая каждый повторный бросок . Это явно непрактично для всех, кроме самого тривиального использования.

Подход 2:

Используйте больше битов: вместо 3 битов используйте 4. Это дает 16 возможных результатов. Конечно, перекатывание в любое время, когда результат больше 5, ухудшает ситуацию (10/16 = 62,5%), так что само по себе это не поможет.

Обратите внимание, что 2 * 6 = 12 <16, поэтому мы можем безопасно принять любой результат, меньший 12, и уменьшить его по модулю 6, чтобы равномерно распределить результаты. Остальные 4 результата должны быть отброшены, а затем повторно свернуты, как в предыдущем подходе.

Сначала звучит хорошо, но давайте проверим математику:

4 discarded results / 16 possibilities = 25%

В этом случае 1 дополнительный бит совсем не помог !

Этот результат неудачный, но давайте попробуем еще раз с 5 битами:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Определенное улучшение, но не достаточно хорошее во многих практических случаях. Хорошая новость заключается в том, что добавление большего количества битов никогда не увеличит шансы на то, что они будут выброшены и переброшены . Это верно не только для игры в кости, но и во всех случаях.

Однако, как показано , добавление 1 дополнительного бита может ничего не изменить. Фактически, если мы увеличим наш бросок до 6 битов, вероятность останется 6,25%.

Это вызывает 2 дополнительных вопроса:

1. Если мы добавим достаточно битов, есть ли гарантия, что вероятность сброса уменьшится?
2. Сколько бит достаточно в общем случае?

Общее решение

К счастью, ответ на первый вопрос - да. Проблема с 6 состоит в том, что 2 ^ x mod 6 переворачивается между 2 и 4, которые по совпадению кратны 2 друг от друга, так что для четного x> 1,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Таким образом, 6 является скорее исключением, чем правилом. Можно найти более крупные модули, которые дают последовательные степени 2 таким же образом, но в конечном итоге это должно обернуться, и вероятность сброса будет уменьшена.

Без дополнительных доказательств, как правило, использование двойного числа требуемых бит обеспечит меньшую, обычно незначительную, вероятность сброса.

Доказательство концепции

Вот пример программы, которая использует libcrypo для OpenSSL для предоставления случайных байтов. При компиляции не забудьте указать ссылку на библиотеку, с -lcryptoкоторой большинство из них должны иметь доступ.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

Я призываю играть с MODULUSи ROLLSзначениями , чтобы увидеть , сколько повторных рулоны на самом деле произошли в большинстве условий. Скептик может также пожелать сохранить вычисленные значения в файл и убедиться, что распределение выглядит нормальным.

Есть две обычные жалобы с использованием по модулю.

• один действителен для всех генераторов. Это легче увидеть в предельном случае. Если ваш генератор имеет значение RAND_MAX, равное 2 (что не соответствует стандарту C), и вы хотите использовать только 0 или 1 в качестве значения, при использовании modulo будет генерироваться 0 в два раза чаще (когда генератор генерирует 0 и 2), чем будет. генерировать 1 (когда генератор генерирует 1). Обратите внимание, что это верно, как только вы не отбрасываете значения, независимо от того, какое отображение вы используете от значений генератора к требуемому, одно произойдет в два раза чаще, чем другое.

• у некоторых генераторов их менее значимые биты менее случайны, чем у других, по крайней мере, для некоторых из их параметров, но, к сожалению, у этих параметров есть другая интересная характеристика (такая, что RAND_MAX может иметь единицу меньше, чем степень 2). Эта проблема хорошо известна, и в течение длительного времени реализация библиотеки, вероятно, избегала этой проблемы (например, реализация примера rand () в стандарте C использует этот тип генератора, но отбрасывает 16 менее значимых битов), но некоторые любят жаловаться на это и вам может не повезло

Используя что-то вроде

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

генерация случайного числа от 0 до n позволит избежать обеих проблем (и избежать переполнения с помощью RAND_MAX == INT_MAX)

Кстати, в C ++ 11 введены стандартные способы редукции и другие генераторы, кроме rand ().

Решение Марка (принятое решение) почти идеально.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

отредактировано 25 марта 16 в 23:16

Марк Амери 39к21170211

Тем не менее, он имеет оговорку, которая отбрасывает 1 действительный набор результатов в любом сценарии, где RAND_MAX( RM) на 1 меньше, чем кратное N(гдеN = количество возможных действительных результатов).

т. е. когда «количество сброшенных значений» ( D) равно N, тогда они фактически являются допустимым набором (а V)не недействительным набором ( I).

Причиной этого является то, что в какой-то момент Марк теряет из виду разницу между Nи Rand_Max.

Nэто набор действительных членов, состоящий только из положительных целых чисел, поскольку он содержит количество ответов, которые были бы действительными. (например: Set N= {1, 2, 3, ... n })

Rand_max Однако это набор, который (как определено для наших целей) включает любое количество неотрицательных целых чисел.

В его наиболее общей форме, что определяется здесь как Rand Max набор всех действительных результатов, которые теоретически могут включать отрицательные числа или нечисловые значения.

Поэтому Rand_Maxлучше определить его как «Возможные ответы».

Однако Nработает против количества значений в наборе допустимых ответов, поэтому даже как определено в нашем конкретном случае, Rand_Maxбудет значение на единицу меньше, чем общее число, которое он содержит.

Используя решение Марка, значения отбрасываются, когда: X => RM - RM% N

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Как вы можете видеть в приведенном выше примере, когда значение X (случайное число, которое мы получаем из начальной функции) равно 252, 253, 254 или 255, мы отбрасываем его, даже если эти четыре значения составляют действительный набор возвращаемых значений ,

IE: когда счетчик значений Discarded (I) = N (Количество действительных результатов), то Действительный набор возвращаемых значений будет отброшен исходной функцией.

Если мы опишем разницу между значениями N и RM как D, то есть:

D = (RM - N)

Затем, когда значение D становится меньше, Процент ненужных повторных бросков из-за этого метода увеличивается при каждом естественном мультипликате. (Когда RAND_MAX НЕ равен простому числу, это имеет значение)

НАПРИМЕР:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Поскольку процент необходимых Rerolls увеличивается по мере приближения N к RM, это может иметь значение для многих различных значений в зависимости от ограничений системы, в которой он работает, и от искомых значений.

Чтобы отрицать это, мы можем внести простую поправку, как показано здесь:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

Это обеспечивает более общую версию формулы, которая учитывает дополнительные особенности использования модуля для определения ваших максимальных значений.

Примеры использования небольшого значения для RAND_MAX, которое является мультипликативным для N.

Mark'original Версия:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Обобщенная версия 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

Кроме того, в случае, когда N должно быть числом значений в RAND_MAX; в этом случае вы можете установить N = RAND_MAX +1, если только RAND_MAX = INT_MAX.

По циклу вы можете просто использовать N = 1, и любое значение X будет, тем не менее, принято и вставлять оператор IF для вашего окончательного множителя. Но, возможно, у вас есть код, который может иметь вескую причину для возврата 1, когда функция вызывается с n = 1 ...

Поэтому может быть лучше использовать 0, что обычно дает ошибку Div 0, когда вы хотите иметь n = RAND_MAX + 1

Обобщенная версия 2:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

Оба эти решения решают проблему с ненужными отклоненными действительными результатами, которые произойдут, когда RM + 1 является произведением n.

Вторая версия также охватывает сценарий крайнего случая, когда вам нужно n, чтобы равняться общему возможному набору значений, содержащихся в RAND_MAX.

Модифицированный подход в обоих случаях одинаков и позволяет найти более общее решение необходимости предоставления действительных случайных чисел и минимизации отброшенных значений.

Чтобы повторить:

Основное общее решение, которое расширяет пример знака:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

 x %= n;

Расширенное общее решение, которое допускает один дополнительный сценарий RAND_MAX + 1 = n:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

    x %= n;
} else {
    x = rand();
}

В некоторых языках (особенно в интерпретируемых) выполнение вычислений операции сравнения вне условия while может привести к более быстрым результатам, поскольку это однократное вычисление независимо от того, сколько повторных попыток требуется. YMMV!

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x; // Resulting random number
int y; // One-time calculation of the compare value for x

if n != 0 {
    y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 
    do {
        x = rand();
    } while (x > y);

    x %= n;
} else {
    x = rand();
}

При RAND_MAXзначении 3(в действительности оно должно быть намного выше, чем это, но смещение все еще существует) из этих вычислений имеет смысл, что есть смещение:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

В этом случае % 2вам не следует делать случайное число между 0и 1. Вы можете получить случайное число между 0и2 , тем не % 3менее, потому что в этом случае: RAND_MAXкратно 3.

Другой метод

Существует гораздо проще, но, чтобы добавить к другим ответам, вот мое решение, чтобы получить случайное число между 0иn - 1 , таким образом, nразными возможностями, без смещения.

• количество битов (не байтов), необходимое для кодирования количества возможностей, равно числу битов случайных данных, которые вам понадобятся
• закодировать число из случайных бит
• если это число >= n, перезапустите (не по модулю).

Действительно случайные данные получить нелегко, поэтому зачем использовать больше битов, чем необходимо.

Ниже приведен пример в Smalltalk, использующий кэш битов от генератора псевдослучайных чисел. Я не эксперт по безопасности, поэтому используйте на свой страх и риск.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r

Как следует из принятого ответа , «смещение по модулю» коренится в низком значении RAND_MAX. Он использует чрезвычайно малое значение RAND_MAX(10), чтобы показать, что если бы RAND_MAX было 10, то вы пытались сгенерировать число от 0 до 2, используя%, в результате получились бы следующие результаты:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

Таким образом, есть 4 выхода 0 (шанс 4/10) и только 3 выхода 1 и 2 (шансы 3/10 каждый).

Так что это предвзято. Меньшие числа имеют больше шансов выйти.

Но это проявляется так очевидно, когда RAND_MAXмало . Или, более конкретно, когда число, на которое вы моддируете, велико по сравнению сRAND_MAX.

Гораздо лучшим решением, чем зацикливание (которое безумно неэффективно и даже не следует предлагать), является использование PRNG с гораздо большим выходным диапазоном. Твистер Мерсенн алгоритм имеет максимальную мощность 4294967295. Таким образом, выполнение MersenneTwister::genrand_int32() % 10всех намерений и целей будет равномерно распределено, а эффект смещения по модулю практически исчезнет.

Я только что написал код для метода беспристрастного подбрасывания монет фон Неймана, который теоретически должен устранить любые смещения в процессе генерации случайных чисел. Дополнительную информацию можно найти по адресу ( http://en.wikipedia.org/wiki/Fair_coin )

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}