×

# A small tutorial on BitMasking

 8 4 Hello all,        The programming club of my college is new and students are not familiar with many algorithms yet (including me :)). So they ask me a lot of problems. Among those, most of my friends and juniors have asked me about bitmasking and they can't find many resource on the internet (well, I learnt it online, from codechef). So I have decided to write a small tutorial. N.B. Please point out if anything is wrong or should be presented in a different way. All criticisms are welcome :) Let's begin : Bit masking is used to find all the subsets of an array. In this method, we create a one-to-one mapping between all subsets and the natural numbers. Consider the first eight numbers and their binary representation. 0 - 000 1 - 001 2 - 010 3 - 011 4 - 100 5 - 101 6 - 110 7 - 111 Let's say the contents of the array is {a,b,c} a is at position 1 b is at position 2 c is at position 3 Consider a subset ac. In this subset, the element at first position of the array is taken. The element at second position is ignored. Again the element at third position is taken. Let's write it as : 101 where 1 at a position indicates the element in the array at that position is taken in the subset. 0 means it is ignored. So, 110 will indicate : element at first and second positions are taken, third one is ignored. So the subset it represents is ab. The array {a,b,c} has three elements. So the number of subsets is 2^3 = 8 Let's write all the subsets in the above mentioned binary notation and let's write the binary numbers in their decimal representation 000 - empty set - 0 001 - c - 1 010 - b - 2 011 - bc - 3 100 - a - 4 101 - ac - 5 110 - ab - 6 111 - abc - 7 See all the subsets are covered and each subset is identified by a natural number (including 0) from the set [0,2^n-1], where n is the size of the array. Now let's come to implementation part : We can iterate through all numbers from 0 to 2^n-1 and check which bits are set in the number in its binary form. If a bit is set, we include the element of the array at that position in our present subset. Now, how to check which bit is set? Consider the number 5 (101 in binary). 101 & 001 = 1 (ANDing with 2^0) 101 & 010 = 0 (ANDing with 2^1) 101 & 100 = 1 (ANDing with 2^2) So,if ANDing with 2^x gives 1, then (x+1)th bit from right (counting starting at 1) is set. C/C++, java gives shift operator (<<) (I don't know about other programming languages). 1<

 2 @dragonemperor, I think there is a small bug in the pseudo code. The condition in outer for loop would not consider the last integer i.e. pow(2,n)-1 the correct code would be for(mask=0 ; mask <= pow(2,n) - 1 ;mask++) answered 08 Jan '17, 16:45 228●1●10 accept rate: 10%
 0 Good initiative answered 25 Oct '15, 22:01 4★gkcs 2.6k●1●11●27 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×703
×132

question asked: 25 Oct '15, 16:24

question was seen: 2,087 times

last updated: 08 Jan '17, 16:46