Uma bitmask é o uso de variáveis inteiras como conjuntos de booleanos.
A vantagem está na poupança de memória (apenas 1 bit por elemento) e na extrema rapidez das operações. Estas duas características são ideais para usar nos concursos.
A maior parte dos excertos de código são da secção 2.2 do livro do Halim, mas juntei alguns outros e um exemplo mais completo.
No Java temos quatro tipos de inteiros
byte b = 36; // 8 bits
short s = 36; // 16 bits
int i = 36; // 32 bits
long lg = 36L; // 64 bits
que podemos usar consoante as nossas necessidades.
O Java fornece vários operadores para lidar com bits. Dois deles fazer shift de bits para a esquerda (<<) e para a direita (>>) que correspondem a multiplicações e divisões inteiras por potências de dois.
Alguns exemplos:
// Multiply by a power of 2
System.out.printf("%d * 4 = %d\n", b, b<<2);
// Divide by a power of 2
System.out.printf("%d / 4 = %d\n", s, s>>2);
// Multiply by 10: 10x = 8x + 2x
System.out.printf("%d * 10 = %d\n", i, (i<<3) + (i<<1));
// Multiply by 3.5: 3.5x = (8x-x)/2
System.out.printf("%d * 3.5 = %d\n", lg, ((lg<<3)-lg)>>1);
36 * 4 = 144
36 / 4 = 9
36 * 10 = 360
36 * 3.5 = 126
Podemos comparar a velocidade entre o uso destas operações e os operadores normais:
long startTime = System.currentTimeMillis();
long total = 0;
for (int k = 0; k < 5000000; k++)
total = k*10;
System.out.println("Time Elapsed: " + (System.currentTimeMillis() - startTime) + "ms");
Time Elapsed: 11ms
startTime = System.currentTimeMillis();
total = 0;
for (int k = 0; k < 5000000; k++)
total = (k<<3) + (k<<1);
System.out.println("Time Elapsed: " + (System.currentTimeMillis() - startTime) + "ms");
Time Elapsed: 8ms
O Java também possui operadores lógicos bit a bit, o not (~), o and (&), o or (|) e o xor (^):
// ~ -- bitwise NOT
short s1 = 7;
System.out.printf("~%d = %d\n", s1, ~s1); // 00000111 => 11111000 (first bit == sign)
// & -- bitwise AND
System.out.printf("%d & %d = %d\n", 7, 3, 7&3);
// | -- bitwise OR
System.out.printf("%d | %d = %d\n", 7, 3, 7|3);
// ^ -- bitwise XOR
System.out.printf("%d ^ %d = %d\n", 7, 3, 7^3);
~7 = -8
7 & 3 = 3
7 | 3 = 7
7 ^ 3 = 4
Com estes operadores podemos manipular determinados bits, sem mudar os restantes:
//turn on a specific bit (starts at index 0)
int bit=3;
System.out.printf("%s with %dth bit on is %s\n",
Integer.toBinaryString(s), bit+1, Integer.toBinaryString( s|(1<<bit) ));
//turn off a specific bit (starts at index 0)
bit=2;
System.out.printf("%s with %dth bit off is %s\n",
Integer.toBinaryString(s), bit+1, Integer.toBinaryString( s&~(1<<bit) ));
//check if a certain bit is on (starts at index 0)
bit=2;
System.out.printf("Has %s the %dth bit on? %s\n",
Integer.toBinaryString(s), bit+1, (s&(1<<bit))!=0 );
//flip a certain bit (starts at index 0)
bit=2;
System.out.printf("%s with the %dth flipped is %s\n",
Integer.toBinaryString(s), bit+1, Integer.toBinaryString( s^(1<<bit) ));
//get least significant bit == 1 (starts at index 0)
System.out.printf("least significant bit of %s at bit %s\n",
Integer.toBinaryString(s), s&-s );
100100 with 4th bit on is 101100
100100 with 3th bit off is 100000
Has 100100 the 3th bit on? true
100100 with the 3th flipped is 100000
least significant bit of 100100 at bit 4
Outras operações avulsas (ver mais aqui)
// check if integers have opposite signs
short x=3, y=-3;
System.out.printf("%d has opposite sign of %d? %s\n", x, y, (x^y)<0 );
3 has opposite sign of -3? true
///////////////////////////////////////
// check if value is 2^x (includes zero)
System.out.printf("%d is a power of 2? %s\n", x, (x&(x-1)) == 0 );
3 is a power of 2? false
///////////////////////////////////////
// counting bits
int c,x1=x; for(c=0; x1!=0; x1>>=1) c += x1 & 1;
System.out.printf("%d has %d bits 1\n", x, c );
3 has 2 bits 1
///////////////////////////////////////
// get the next power of 2 (for integers, 32 bits)
static int nextPower(int v) {
v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
return ++v;
}
int v=1034;
System.out.printf("next power of 2 of %d is %d\n", v, nextPower(v));
next power of 2 of 1034 is 2048
///////////////////////////////////////
// compute next lexicographic permutation, maintaining the number of bits 1
v = 19;
System.out.printf("next permutation of %s is %s\n",
Integer.toBinaryString(v),
Integer.toBinaryString(nextBitPermutation(v)));
next permutation of 10011 is 10101
///////////////////////////////////////
// compute next grey code, ie, a representation where two successive values differ in only one bit
// eg for 4 bits: 0000->0001->0011->0010->0110->0111 ...
// number of bits 1 is invariant
static int nextBitPermutation(int v) {
int t = (v | (v - 1)) + 1;
return t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
IntStream.range(1,15).forEach(n -> System.out.printf("%s -> ", Integer.toBinaryString(grey(n)) ));
System.out.println("...");
0 -> 1 -> 11 -> 10 -> 110 -> 111 -> 101 -> 100 -> 1100 -> 1101 -> 1111 -> 1110 -> 1010 -> 1011 -> ...
Vejamos um exemplo de uso (ref).
Seja o seguinte problema: há n pessoas (n<=10) que possuem diferentes chapéus (há 100 tipos diferentes). Queremos saber de quantas formas diferentes podemos atribuir um chapéu a cada pessoa de forma a que nenhum par de pessoas use o mesmo tipo de chapéu. Por exemplo, seja esta instância de problema:
3
5 100 1
2
5 100
ou seja, há três pessoas, a 1ª tem chapéus do tipo 1, 5 e 100, a 2ª tem apenas um chapéu de tipo 2 e a 3ª pessoa tem chapéus do tipo 5 e 100.
Nesta instância há quatro soluções diferentes: as atribuições (5, 2, 100), (100, 2, 5), (1, 2, 5) e (1, 2, 100).
Como este número pode crescer imenso, pede-se para devolver o valor total módulo 1000000007.
Este é um problema onde temos de verificar todos os subconjuntos de atribuições de chapéus pelas n pessoas.
A nossa matriz de soluções sols[i][j] vai representar o seguinte: i corresponde ao conjunto de pessoas que estão a usar chapéu e j representa quantos tipos de chapéus já foram usados (dos tipos 1 a j). Vamos guardar estes valores porque caso contrário eles seriam calculados repetidamente.
A primeira dimensão da matriz é complexa, representa um conjunto de valores booleanos que guardam respostas como 'a i-ésima pessoa está a usar chapéu?'. Para tal vamos usar um bitmask que pode ter até 10 bits (o número máximo de pessoas). Ou seja, teremos 2^10 = 1024 sub-conjuntos possíveis. Isto significa que a primeira dimensão está a indexar a um conjunto de booleanos! Esta é uma das vantagens dos bitmasks.
Reparem que não sabemos exactamente quem está a usar qual chapéu (isso não é pedido no enunciado) apenas sabemos que todos os chapéus de índices 1 a j já não podem ser escolhidos nos cálculos adiante.
Este é o início da classe:
public class UniqueCaps {
static final int TOTAL_CAPS = 101;
static final long MOD = 1_000_000_007;
// define array caps where we keep who can wear cap i
static List<Integer>[] caps;
// In sols[i][j], i denotes the bitmask, ie, who are wearing caps
// and j denotes the number of caps 1 to j used so far,
// with the restriction that no one is wearing the same cap
// There are up to 10 persons (2^10 = 1024) and 100 caps
static long[][] sols;
// init data structures
static {
caps = new List[TOTAL_CAPS];
for(int i=1; i<TOTAL_CAPS; i++)
caps[i] = new LinkedList<Integer>();
sols = new long[1025][TOTAL_CAPS]; // let's start indexes at 1
for(int i=0; i<1025; i++)
for(int j=0; j<TOTAL_CAPS; j++)
sols[i][j] = -1L;
}
static int allmask; // all are wearing caps, ie, all bits are set to 1
A ideia principal para calcular as soluções é a seguinte: solve(int bitmask, int i) significa que dado o conjunto de atribuições corrente (bitmask) queremos tratar o chapéu de tipo i (assumindo que já tratamos os chapéus de tipo 1 a i-1).
Para tal, se todas as pessoas já têm chapéus, já temos uma solução. Senão, há que considerar as seguintes hipóteses:
O resultado será a soma de todas estas respostas.
Vejamos a implementação do método solve:
// bitmask is the set of persons in consideration
// the caps are already processed from 1 to i-1
// complexity O(2^nPersons * TOTAL_CAPS)
private static long solve(int bitmask, int i) {
if (allmask == bitmask) // all persons are using caps, we are done
return 1;
if (i>=TOTAL_CAPS) // not all are wearing caps, but no caps left
return 0; // so, no solution was found
if (sols[bitmask][i] != -1) // solution already found
return sols[bitmask][i];
// if we don't include this cap, how many solutions are there?
long nSols = solve(bitmask, i+1);
// assign cap i to every person that has it
for(int person : caps[i]) {
// if this person is already wearing a cap, go to next one
if ((bitmask & (1 << (person-1))) != 0)
continue;
// otherwise, assign it, and solve for the remaining caps
int newBitmask = bitmask | (1 << (person-1));
nSols += solve(newBitmask, i+1);
nSols %= MOD;
}
return sols[bitmask][i] = nSols;
}
O que sobra é ler o input e invocar o solve:
public static void main(String[] args) {
if (!new Object(){}.getClass().getName().contains("Main"))
// if true: read from files; else: read from System.in
try {
System.setIn (new FileInputStream("data/uniquecaps.in.txt" ));
System.setOut(new PrintStream("data/uniquecaps.out.txt") );
} catch (Exception e) {}
///////////////////////
Scanner sc = new Scanner(System.in);
int nPersons = sc.nextInt();
// read caps
sc.nextLine(); // consume first newline
for(int person=1; person<=nPersons; person++) {
int[] caps_i = Arrays.stream(sc.nextLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
for(int cap : caps_i)
caps[cap].add(person);
}
allmask = (1<<nPersons) - 1; // set bits to 1
System.out.println( solve(0,1) );
}
} // end class
Para consolidar esta matéria, resolvam o UVa 11926 usando um bitmask com 1 milhão de bits.