Monday, September 4, 2017

Bit & BitSet


Bit and BitSet are very commonly used in profiling your java code. Also, In interviews, your interviwers may also ask some questions about it . Raw bit manipulations are mostly tested in job interviews which are hard for most of us but BitSet are mostly used in real projects which is easy to use.


Basics

And(&)
0 & 0= 0
1 & 0 = 0
0 & 1= 0
1 & 1 =1
Or (|)
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1
Xor (^)
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 0

x << y means x shifted by y bits to the left. for example :
               00011001 << 2  = 00000110
               00011001 << 4  = 10010000
x >> y means x shifted y bits to the right , for example :
               00011001 >> 2 = 00000110
               00011001 >> 4 = 00000001

Interview Questions

You have two 32-bit numbers, N and M and 2 bit positions, i and j .write a method to set all bits  between i and j in N  equal to M(eg: M becomes a subString of N located at i and starting at j)
Example : Input : 10000000000 , M = 10101, i = 2, j = 6
                   Output : N = 10001010100


public static int updateBits(int n , int m, int i, int j) {
  int max = ~0; // All 1's
  
  // 1's through position j, then 0's
  int left = max - ((1 << j) - 1);
  
  // 1's after position i
  int right = ((1 << i) - 1);
  
  // 1's , with 0's between i and j 
  int mask = left | right;
  
  // clear i through j, then put m in there
  return (n & mask) | (m << i);
  
 }

Bitset : BitSet is introduced in Java 1.1 and it only has a few of methods which are commonly used. But These methods are very helpful in tuning our application expecially in Comparison & Filtering.

Previously, if the criteria in our if-statement is comparison, for example

List<Bid> candidateBid = new ArrayList<>();
PotentialBid potentialBid = new PotentialBid();
candidateBid.stream()
	.filter(x -> x.getAutionType() == potentialBid.getAutionType()) // int
	.filter(x -> x.getCountryCode() == potentialBid.getCountryCode()); // String

Improvement makes matching faster :


BitSet candidateBid = new BitSet(); // imagine it has datas
candidateBid.and(autionTypeMatch.getCandidates(bid)); // get intersection set == filter
candidateBid.and(countryMatcher.getCandidates(bid)); // get intersection set == filter

Bitset can hold 2^31 -1 elements , in other word , it can hold huge amount of data.
So , There are still other applications of BitSet , like save a billion data....

No comments:

Post a Comment

Add Loading Spinner for web request.

when web page is busily loading. normally we need to add a spinner for the user to kill their waiting impatience. Here, 2 steps we need to d...