Skip to content

Instantly share code, notes, and snippets.

@aaccioly aaccioly/BitPeriod2.java Secret
Last active Aug 29, 2015

Embed
What would you like to do?
Tamanho do Período
/**
* 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);
}
}
}
/**
* 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);
}
}
}
/**
* 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);
}
}
}
public interface Question2 {
int solution(int n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.