
By bmerry TopCoder Member Introduction Most of the optimizations that go into TopCoder challenges are highlevel; that is, they affect the algorithm rather than the implementation. However, one of the most useful and effective lowlevel optimizations is bit manipulation, or using the bits of an integer to represent a set. Not only does it produce an orderofmagnitude improvement in both speed and size, it can often simplify code at the same time. I'll start by briefly recapping the basics, before going on to cover more advanced techniques. The basics At the heart of bit manipulation are the bitwise operators & (and),  (or), ~ (not) and ^ (xor). The first three you should already be familiar with in their boolean forms (&&,  and !). As a reminder, here are the truth tables:
The bitwise versions of the operations are the same, except that instead of interpreting their arguments as true or false, they operate on each bit of the arguments. Thus, if A is 1010 and B is 1100, then
In general, we will use an integer to represent a set on a domain of up to 32 values (or 64, using a 64bit integer), with a 1 bit representing a member that is present and a 0 bit one that is absent. Then the following operations are quite straightforward, where ALL_BITS is a number with 1's for all bits corresponding to the elements of the domain:
In this section I'll consider the problems of finding the highest and lowest 1 bit in a number. These are basic operations for splitting a set into its elements. Finding the lowest set bit turns out to be surprisingly easy, with the right combination of bitwise and arithmetic operators. Suppose we wish to find the lowest set bit of x (which is known to be nonzero). If we subtract 1 from x then this bit is cleared, but all the other one bits in x remain set. Thus, x & ~(x  1) consists of only the lowest set bit of x. However, this only tells us the bit value, not the index of the bit. If we want the index of the highest or lowest bit, the obvious approach is simply to loop through the bits (upwards or downwards) until we find one that is set. At first glance this sounds slow, since it does not take advantage of the bitpacking at all. However, if all 2^{N} subsets of the Nelement domain are equally likely, then the loop will take only two iterations on average, and this is actually the fastest method. The 386 introduced CPU instructions for bit scanning: BSF (bit scan forward) and BSR (bit scan reverse). GCC exposes these instructions through the builtin functions __builtin_ctz (count trailing zeros) and __builtin_clz (count leading zeros). These are the most convenient way to find bit indices for C++ programmers in TopCoder. Be warned though: the return value is undefined for an argument of zero. Finally, there is a portable method that performs well in cases where the looping solution would require many iterations. Use each byte of the 4 or 8byte integer to index a precomputed 256entry table that stores the index of the highest (lowest) set bit in that byte. The highest (lowest) bit of the integer is then the maximum (minimum) of the table entries. This method is only mentioned for completeness, and the performance gain is unlikely to justify its use in a TopCoder match. Counting out the bits One can easily check if a number is a power of 2: clear the lowest 1 bit (see above) and check if the result is 0. However, sometimes it is necessary to know how many bits are set, and this is more difficult. GCC has a function called __builtin_popcount which does precisely this. However, unlike __builtin_ctz, it does not translate into a hardware instruction (at least on x86). Instead, it uses a tablebased method similar to the one described above for bit searches. It is nevertheless quite efficient and also extremely convenient. Users of other languages do not have this option (although they could reimplement it). If a number is expected to have very few 1 bits, an alternative is to repeatedly extract the lowest 1 bit and clear it. All the subsets A big advantage of bit manipulation is that it is trivial to iterate over all the subsets of an Nelement set: every Nbit value represents some subset. Even better, if A is a subset of B then the number representing A is less than that representing B, which is convenient for some dynamic programming solutions. It is also possible to iterate over all the subsets of a particular subset (represented by a bit pattern), provided that you don't mind visiting them in reverse order (if this is problematic, put them in a list as they're generated, then walk the list backwards). The trick is similar to that for finding the lowest bit in a number. If we subtract 1 from a subset, then the lowest set element is cleared, and every lower element is set. However, we only want to set those lower elements that are in the superset. So the iteration step is just i = (i  1) & superset. Even a bit wrong scores zero There are a few mistakes that are very easy to make when performing bit manipulations. Watch out for them in your code.
There are a few other tricks that can be done with bit manipulation. They're good for amazing your friends, but generally not worth the effect to use in practice.
Sample problems TCCC 2006, Round 1B Medium For each city, keep a bitset of the neighbouring cities. Once the partbuilding factories have been chosen (recursively), ANDing together these bitsets will give a bitset which describes the possible locations of the partassembly factories. If this bitset has k bits, then there are ^{k}C_{m} ways to allocate the partassembly factories. TCO 2006, Round 1 Easy The small number of nodes strongly suggests that this is done by considering all possible subsets. For every possible subset we consider two possibilities: either the smallestnumbered node does not communicate at all, in which case we refer back to the subset that excludes it, or it communicates with some node, in which case we refer back to the subset that excludes both of these nodes. The resulting code is extremely short: static int dp[1 << 18]; int SeparateConnections::howMany(vector <string> mat) { int N = mat.size(); int N2 = 1 << N; dp[0] = 0; for (int i = 1; i < N2; i++) { int bot = i & ~(i  1); int use = __builtin_ctz(bot); dp[i] = dp[i ^ bot]; for (int j = use + 1; j < N; j++) if ((i & (1 << j)) && mat[use][j] == 'Y') dp[i] = max(dp[i], dp[i ^ bot ^ (1 << j)] + 2); } return dp[N2  1]; }SRM 308, Division 1 Medium The board contains 36 squares and the draughts are indistinguishable, so the possible positions can be encoded into 64bit integers. The first step is to enumerate all the legal moves. Any legal move can be encoded using three bitfields: a before state, an after state and a mask, which defines which parts of the before state are significant. The move can be made from the current state if (current & mask) == before; if it is made, the new state is (current & ~mask)  after. SRM 320, Division 1 Hard The constraints tell us that there are at most 8 columns (if there are more, we can swap rows and columns), so it is feasible to consider every possible way to lay out a row. Once we have this information, we can solve the remainder of the problem (refer to the match editorial for details). We thus need a list of all nbit integers which do not have two adjacent 1 bits, and we also need to know how many 1 bits there are in each such row. Here is my code for this: for (int i = 0; i < (1 << n); i++) { if (i & (i << 1)) continue; pg.push_back(i); pgb.push_back(__builtin_popcount(i)); }


Home 
About TopCoder 
Press Room 
Contact Us 
Careers 
Privacy 
Terms
Competitions  Cockpit 
Copyright TopCoder, Inc. 2001 