Tamanho do Período

BitPeriod2.java

/**
 * Resposta da pergunta sobre período de uma String binária
 *
 * @author utluiz
 * 
 * @see <a href="http://pt.stackoverflow.com/questions/14970">Retornar o tamanho
 * do "período" de uma cadeia de bits</a>
 */
public class BitPeriod2 implements Question2 {

    @Override
    public int solution(int n) {
        // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
        if (n < 2) {
            return -1;
        }

        // inicialização de variáveis
        String s = Integer.toBinaryString(n);
        byte[] bytes = s.getBytes();
        int t = bytes.length;

        // período inicial
        int p = 1;

        // verifica se o período se repete pelo menos uma vez
        boolean diferente;
        do {
            diferente = false;
            int qp = t / p; // quantidade de períodos
            if (t % qp > 0) {
                qp++; //somar 1 para comparar os caracteres de resto no final
            }
            // verifica se a repetição ocorre
            for2:
            for (int k = 0; k < p; k++) {
                for (int j = 1; j < qp; j++) {
                    if (k + p * j < t && bytes[k] != bytes[k + p * j]) {
                        diferente = true;
                        break for2;
                    }
                }
            }

            //se não encontrou repetição, tenta um período menor
            if (diferente) {
                p++;
            }
        } while (diferente && p <= t / 2);

        return p > t / 2 ? -1 : p;
    }
    
    public static void main(String[] args) {
        final BitPeriod bitPeriod = new BitPeriod();
        for (int i = 0; i < 100; i++) {
            long nano = System.nanoTime();
            for (int j = 0; j < 100000; j++) {
                bitPeriod.solution(10);
                bitPeriod.solution(187);
                bitPeriod.solution(955);
                bitPeriod.solution(1000000000);
                bitPeriod.solution(0b10101000001010100000);
            }
            System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
        }
    }

}

BitPeriod3.java

/**
 * Resposta da pergunta sobre período de uma String binária.
 *
 * <p>
 * Essa versão usa força bruta e manipulação de bits, e é atualmente a
 * implementação mais rápida do algoritmo.
 *
 * @author Anthony Accioly
 *
 * @see <a href="http://pt.stackoverflow.com/questions/14970">Retornar o tamanho
 * do "período" de uma cadeia de bits</a>
 */
public class BitPeriod3 implements Question2 {

    @Override
    public int solution(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n precisa ser positivo");
        }
        int result = - 1;
        // tamanho da cadeia de bits
        final int q = 32 - Integer.numberOfLeadingZeros(n);
        // cada periodo entre p 1 e tamanho da cadeia / 2
        for (int p = 1; p <= q / 2 && result == -1; p++) {
            // primeiros p bits
            final int k = n >> q - p;
            if (n == constroiPeriodo(k, p, q)) {
                result = p;
            }
        }
        return result;
    }

    /**
     * Constrói uma string de tamanho <code>q</code> a partir da repetição de
     * uma cadeia de <code>bits</code>.
     *
     * @param k string de bits
     * @param p tamanho do período
     * @param q tamanho da string de bits
     *
     * @return a cadeia de <code>bits</code> repetida periodicamente ate o
     * <code>q</code> elemento.
     */
    private int constroiPeriodo(int k, int p, int q) {
        int result = 0;
        // periodos inteiros
        for (int i = 0; i < q; i += p) {
            result = result << p | k;
        }
        // ultimo periodo parcial
        final int mod = q % p;
        if (mod != 0) {
            result = result >> p - mod;
        }

        return result;
    }

    public static void main(String[] args) {
        final BitPeriod3 bitPeriod = new BitPeriod3();
        for (int i = 0; i < 100; i++) {
            long nano = System.nanoTime();
            for (int j = 0; j < 100000; j++) {
                bitPeriod.solution(10);
                bitPeriod.solution(187);
                bitPeriod.solution(955);
                bitPeriod.solution(1000000000);
                bitPeriod.solution(0b10101000001010100000);
            }
            System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
        }
    }

}

BitPeriod4.java

/**
 * Resposta da pergunta sobre período de uma String binária.
 *
 * <p>
 * Essa versão usa apenas manipulação de bits.
 *
 * @author utluiz
 * @author a.accioly
 *
 * @see <a href="http://pt.stackoverflow.com/questions/14970">Retornar o tamanho
 * do "período" de uma cadeia de bits</a>
 */
public class BitPeriod4 implements Question2 {

    @Override
    public int solution(int n) {
        // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
        if (n < 2) {
            return -1;
        }

        // inicialização de variáveis
        final int t = 32 - Integer.numberOfLeadingZeros(n);

        // descarta bits não significantes
        final int s = n >>> Integer.numberOfTrailingZeros(n);

        // período inicial
        int p = 1;

        // verifica se o período se repete pelo menos uma vez
        boolean diferente;
        do {
            diferente = false;
            int qp = t / p; // quantidade de períodos
            if (t % qp > 0) {
                qp++; //somar 1 para comparar os caracteres de resto no final
            }
            // verifica se a repetição ocorre
            for2:
            for (int k = 0; k < p; k++) {
                final byte kBit = getBit(s, k);
                for (int j = 1; j < qp; j++) {
                    if (k + p * j < t && kBit != getBit(s, k + p * j)) {
                        diferente = true;
                        break for2;
                    }
                }
            }

            //se não encontrou repetição, tenta um período menor
            if (diferente) {
                p++;
            }
        } while (diferente && p <= t / 2);

        return p > t / 2 ? -1 : p;
    }

    private byte getBit(int n, int pos) {
        return (byte) ((n >> pos) & 1);
    }

    public static void main(String[] args) {
        final BitPeriod4 bitPeriod = new BitPeriod4();
        for (int i = 0; i < 100; i++) {
            long nano = System.nanoTime();
            for (int j = 0; j < 100000; j++) {
                bitPeriod.solution(10);
                bitPeriod.solution(187);
                bitPeriod.solution(955);
                bitPeriod.solution(1000000000);
                bitPeriod.solution(0b10101000001010100000);
            }
            System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
        }
    }

}

Question2.java

public interface Question2 {
   int solution(int n);
}