![]() ![]() They’re good for amazing your friends, but generally not worth the effect to use in practice. There are a few other tricks that can be done with bit manipulation. The most common use for shifting is to access a particular bit, for example, 1 > will sign-extend values (which is probably not what you want), but the Java-specific operator > will shift in zeros. You can think of left-shifting by b as multiplication by 2b and right-shifting as integer division by 2b. For non-negative values (which are the only ones we’re interested in), the newly exposed bits are filled with zeros. ![]() The former shifts all the bits in a to the left by b positions the latter does the same but shifts right. The other two operators we will need are the shift operators a > b. ~A = 11110101 (the number of 1′s depends on the type of A). The bit-wise 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. As a reminder, here are the truth tables: A The first three you should already be familiar with in their boolean forms (&, || and !). ![]() The basicsĪt the heart of bit manipulation are the bit-wise operators & (and), | (or), ~ (not) and ^ (xor). I’ll start by briefly recapping the basics, before going on to cover more advanced techniques. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time. However, one of the most useful and effective low-level optimizations is bit manipulation, or using the bits of an integer to represent a set. Most of the optimizations that go into Topcoder challenges are high-level that is, they affect the algorithm rather than the implementation. Discuss this article in the forums Introduction ![]()
0 Comments
Leave a Reply. |