![]() ![]() So if x is a power of 2 then x & (x-1) will be 0. If the number is neither zero nor a power of two, it will have 1 in more than one place. Properties for numbers which are powers of 2, is that they have one and only one bit set in their binary representation. x & (x-1) will have all the bits equal to the x except for the rightmost 1 in x. It might not seem obvious with these examples, but binary representation of (x-1) can be obtained by simply flipping all the bits to the right of rightmost 1 in x and also including the rightmost 1. (x-1) will have all the bits same as x, except for the rightmost 1 in x and all the bits to the right of the rightmost 1. Now think about the binary representation of (x-1). Consider a number x that we need to check for being a power for 2. The same problem can be solved using bit manipulation. Time complexity of the above code is O(logN). Let’s code it.Ībove function will return true if x is a power of 2, otherwise false. If we end up with a 1 then N is power of 2, otherwise not. ![]() Simple solution to this problem is to repeated divide N by 2 if N is even. Lets discuss some algorithms based on bitwise operations:ġ) How to check if a given number is a power of 2 ?Ĭonsider a number N and you need to find if N is a power of 2. Note: All left and right side taken in this article, are taken with reference to the reader. Right shift is equivalent to dividing the bit pattern with 2k ( if we are shifting k bits ).īitwise operators are good for saving space and sometimes to cleverly remove dependencies. Left Shift ( > ): Right shift operator is a binary operator which shift the some number of bits, in the given bit pattern, to the right and append 1 at the end. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1. XOR ( ^ ): Bitwise XOR also takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1. OR ( | ): Bitwise OR is also a binary operator that operates on two equal-length bit patterns, similar to bitwise AND. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0. Lets take an example.ĪND ( & ): Bitwise AND is a binary operator that operates on two equal-length bit patterns. Bitwise NOT is nothing but simply the one’s complement of a number. NOT ( ~ ): Bitwise NOT is an unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa. Bit operations are fast and can be used in optimizing time complexity. These bit operations operate on the individual bits of the bit patterns. There are different bitwise operations used in the bit manipulation. = 1 * 2 4 + 0 * 2 3 + 1 * 2 2 + 0 * 2 1 + 0 * 2 0įor characters, we use ASCII representation, which are in the form of integers which again can be represented using bits as explained above. We all know that 1 byte comprises of 8 bits and any integer or character can be represented using bits in computers, which we call its binary form(contains only 1 or 0) or in its base 2 form. Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level. In order to encode, decode or compress files we have to extract the data at bit level. Operations with bits are used in Data compression (data is compressed by converting it from one representation to another, to reduce the space), Exclusive-Or Encryption (an algorithm to encrypt the data for safety issues). In some cases, a programmer needs to go beyond this - that is to say that in a deeper level where the importance of bits is realized. ![]() Working on bytes, or data types comprising of bytes like ints, floats, doubles or even data structures which stores large amount of bytes is normal for a programmer. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |