Well, before I start off with the actual content, lets thank and congratulate Mr Kapil Garg for his ingenious solution to the seven points problem. His was the first reply that I received. So I can safely assume that its only him (of course, within the domain of people who saw the problem) who has solved the problem.
Well, just a small explanation on the solution. 4 equilateral triangles ABD, AEG, CDB, FEG with unit sides, are drawn such that FC is at distance 1. Attached is the solution sent by Kapil:
Okk, so lets come back to the issue of bits and bytes.
Well, just a small explanation on the solution. 4 equilateral triangles ABD, AEG, CDB, FEG with unit sides, are drawn such that FC is at distance 1. Attached is the solution sent by Kapil:
Okk, so lets come back to the issue of bits and bytes.
This just implies n bits can help me represent any number till 2^n -1.
Now whenever you see a question (People who are belling the CAT this year, please notice!!!) like, " I have 127 coins of Re 1. How many minimum bags I need to make (and of what denominations) so that I can share any amount till Rs 127.
The answer is: just find binary representation of 127 which I guess is 1111111 and that is 7 bits. So, we need to make 7 bags of 1,2,4,8,16,32,64 coins each and we can satisfy any demand till Rs 127. Infact, any demand from 64 to 127 will require 7 bags at least since the binary representation of 64 requires 7 bits.
This makes me go back to the question in my class 10 Physics Lab. Why are the denominations in a weight box of a mass-balance in ratio 1:2:2:5? The answer we were told was that this ratio can satisfy all weight combinations from 1 to 10. If I could go back, I would have said, "mam it can also be in 1,2,4,8 and with my combination you can satisfy all weights till 1 to 15".
Anyways, so simple operations on bits, We all know about them. And, OR, XOR, NOT. I dont need to tell all those.
Ok, a very interesting question, " Tell me how can you find the last set bit in a binary representation of a number. What I mean is for 2 (10) answer would be 2nd bit, for 5(101) answer would be first bit and for 10(1010) answer would be second bit. Give me an expression that helps me single out only the last set bit of a number n." Hint : Use & and - (this is not logical ~ operation.)
Well, a very important manipulation done with bits is set and subset selection. Say I have n elements (n<32) and I want to generate all possible subsets of these 32 elements. From basic perm and comb theory, the answer is 2^n subsets. Generating all these sets with hands is easy. With computers, it easier! Just loop over i from 0 to 2^n-1 and see the pattern of set bits in i. A jth set bit in i means that jth element is selected. Hence for i=0, no set bit, means no element is selected. And for i=3 (11), both 1st and 2nd elements are selected. So, say I want to print all the possible subsets of elements in an array. So the pseudo code would be
A[1...n]
for i=0 to 1<< n ....... set bits of i represents selected elements in the current subset
for j=0 to n.................... j is to iterate over all elements
if( i & j) ............ (checking if jth element is selected)
{
print A[j];
}
I know it may be difficult to see whats happening. Just iterate it for n=3,4,5 and you will understand the logic behind it. Hence, any integer can be used to depict the subset selection. Hence all set operations are just trivial. Two sub-sets represents by i & j are:
1. mutually exclusive if i & j = 0
2. are same if i = j
3. exhaustive if i | j = 2^n - 1
Just a bit more fascinating is XOR operation. If B is a subset of A, and you want to select elements of A not present in B, the simple operation is A XOR B. For any two sets A and B, the operation A-B is (A XOR B ) & A. If you dont get it, please try seeing with small numbers or else you can always email me at my id.
Well, I hope you remember the puzzle above (written in brown). I will add one more very simple puzzle and a algorithm question to keep you busy while I deal with my end-semester exams.
Puzzle: Find a number N which when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5.
Algorithm puzzle: Give me a good (non-bruteforce please!) algorithm to find the number of set bits in binary representation of a number n.
Happy bit-ing :).
Contact: nitkkr.vivek@gmail.com
