Skip to main content

BIT Masking On Java On Ease

How to count set bits.
For example the number 9 in binary form is : 1001
                  1001
there are 2 set (or 1) bits in 9.

But how can we count them. Using below algo, we can count them

int num = 9;
int count = 0;
while(num > 0) {
count += num & 1;
num >>= 1
}

System.out.println("The output is : " + count);
Answer:
                The output is : 2

1. 1 or Set bit count = num &(num - 1)
2. Find first set bit or first 1 bit in binary
3. Bit set in range mask = (1 << (right - left + 1) => mask -= 1;
4. int index = x&-x
5. Power of 2 n != 0 && ((n & (n - 1)) == 0);
6. public static int findBitVal(int num, int i) { return (num & (1 << i)) == 0 ? 0 : 1; }
7. Num & (1 << i) to check the ith bit is 0 or 1, can also be used to find first 1 (set) in binary Num is integer but in editor when used along with & Java treat it as binary
8. Digit count in binary Int count; while(num > 0){ Num = num/2; Count++; )
9. Find non repeating to odd number of times repeating element
XOR ^= num[i] Xor of 0 is xor Same num’s xor cancel each other 10. Find Element NonRepeating Others Repeating 2 Times
Result = XOR all element of array
Find first 1 in Result
Create arrayList of num of array elements having 1 at same position as it is in result;
Again XOR all element of ArrayList using Result XOR in temp
Now XOR Result and temp
11. Find Element NonRepeating Others Repeating k Times
Create aux 32 bit array
Collect binary 1’s in aux as per position of 1 in element in binary form of array (use find 1 approach to find 1 position of element in binary form) Use modulo k on aux array element 12. Use 2 power multiple by aux element (either 0 or 1) of each element and add in output to find the number
13. Swap 2 numbers a = a ^ b; b = a ^ b; a = a ^ b; 14. Value of ith bit Num & (1 << i) => i is 2 => 10110 & 00100 => 00100 => it is 1
15. Set ith bit to 1
num & (1 << i) => i is 3 => 10110 & 01000 => 11110
16. Set 0 to ith bit
num &(~(1 << i)) => i is 2 => ~00100 => toggle/inverse => 11011 => num = 10110 ======>10110 & 11011 => 10010 long n = 12345;
int digit = 0;
while(n > 0) { n = n/2; digit++; } System.out.println(digit);
n = 12345;
for(int i = 0; i <= 14; i++) { //System.out.println(Integer.toBinaryString(1 << i)); // System.out.println(n & (1 << i)); if((n & (1 << i)) > 0){ System.out.print(i + " "); System.out.println((n & (1 << i))); } } Count of 1
int n = 8;
int count = 0;
while(n > 0) { n = n & (n - 1); count++; } (val >> j) & 1) == 1 Val & (1 << i) ==1 17. Reverse bit unsigned integer
Reverse = num & 1;
Int i = 1;
while(i < 32){ Num = num >> 1; Reverse = reverse << 1; Reverse += (num & 1); } 18. Divide number without division, multiplication or %
Take dividend and divisor
While check is (dividend - divisor ) is great than or equals to 0
Inside take count variable
Take inner while loop and condition check (dividend - (divisor << 1 << count)) is great than or equals to 0
If yes, increment count;
After inner while loop add count value in quotient = quotient + count
Then update dividend by subtracting it with divisor << count (left shift of divisor by count times)
19. Brian Kernighan’s Algorithm:
(num = Num >> 1) & 1 while num is still above 0 then count++;
Set bit difference Xor OR Bit differece
1001101 ^0101011 ------------- 1100110 20. On bit count before nearest power 2 value
For Example for 1 to 11 number 8 is nearest largest 2 power number, so number of set bit before 8 will be 2^(3-1)*3 => 2^2 * 3 => 4 * 3 => 12 set bits
21. So total set bit count from 0 to N is ...lets, nearest power of 2 is x
Formula : 2^(x - 1)*x + (N - 2^x + 1)(i.e this is set bit count from 1 column from s^x to N) + now count remaining set bit from (N - 2^x) values
// to find power 2 number nearest
int x = 0;
int sum = 0;
// find nearest power 2 power
// 1 << 0 is 1, 1 << 1 is 2 , 1 << 2 is 4, i << 3 is 8 while((1 << x) <= N) {
x++; }
------------------------------------ 2 raise to power 3 is 8 and in bits
(1 << 3) = 8 Bit reverse
private static int getRev(int n) { int rev = 0; while(n > 0) { int lb = n & 1; rev |= lb; rev <<= 1; n >>= 1; } rev >>= 1; return rev; }
In XOR of subarray
frequency of element at i-th index is given by (i+1)*(N-i), where N is the size of the array
------------------------------------------------------------------------------------------------------------
22. Bit Tricks for Competitive Programming
In competitive programming or in general some problems seems difficult but can be solved very easily with little bit magic. We have discussed some tricks in below previous post. Bitwise Hacks for Competitive Programming We have considered below facts in this article –
0 based indexing of bits from right to left.
Setting i-th bit means, turning i-th bit to 1 Clearing i-th bit means, turning i-th bit to 0 1) Clear all bits from LSB to ith bit mask = ~((1 << i+1 ) - 1);
x &= mask; Logic: To clear all bits from LSB to i-th bit, we have to AND x with mask having LSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0. Now we can simply take complement of mask to get all first i bits to 0 and remaining to 1.
Example-
x = 29 (00011101) and we want to clear LSB to 3rd bit, total 4 bits
mask -> 1 << 4 -> 16(00010000) mask -> 16 – 1 -> 15(00001111) mask -> ~mask -> 11110000 x & mask -> 16 (00010000) 2) Clearing all bits from MSB to i-th bit
mask = (1 << i) - 1;
x &= mask; Logic: To clear all bits from MSB to i-th bit, we have to AND x with mask having MSB to i-th bit 0. To obtain such mask, first left shift 1 i times. Now if we minus 1 from that, all the bits from 0 to i-1 become 1 and remaining bits become 0.
Example- x = 215 (11010111) and we want to clear MSB to 4th bit, total 4 bits
mask -> 1 << 4 -> 16(00010000)
mask -> 16 – 1 -> 15(00001111)
x & mask -> 7(00000111)
3) Divide by 2
x >>= 1;
Logic: When we do arithmetic right shift, every bit is shifted to right and blank position is substituted with sign bit of number, 0 in case of positive and 1 in case of negative number. Since every bit is a power of 2, with each shift we are reducing the value of each bit by factor of 2 which is equivalent to division of x by 2.
Example-
x = 18(00010010) x >> 1 = 9 (00001001) 4) Multiplying by 2 x <<= 1;
Logic: When we do arithmetic left shift, every bit is shifted to left and blank position is substituted with 0 . Since every bit is a power of 2, with each shift we are increasing the value of each bit by a factor of 2 which is equivalent to multiplication of x by 2.
Example-
x = 18(00010010)
x << 1 = 36 (00100100)
5) Upper case English alphabet to lower case
ch |= ' ';
Logic: The bit representation of upper case and lower case English alphabets are –
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. . . .
Z -> 01011010 z -> 01111010
As we can see if we set 5th bit of upper case characters, it will be converted into lower case character. We have to prepare a mask having 5th bit 1 and other 0 (00100000). This mask is bit representation of space character (‘ ‘). The character ‘ch’ then ORed with mask.
Example-
ch = ‘A’ (01000001)
mask = ‘ ‘ (00100000)
ch | mask = ‘a’ (01100001)
Please refer Case conversion (Lower to Upper and Vice Versa) for details.
6) Lower case English alphabet to upper case
ch &= '_’ ;
Logic: The bit representation of upper case and lower case English alphabets are –
A -> 01000001 a -> 01100001
B -> 01000010 b -> 01100010
C -> 01000011 c -> 01100011
. . . . Z -> 01011010 z -> 01111010
As we can see if we clear 5th bit of lower case characters, it will be converted into upper case character. We have to prepare a mask having 5th bit 0 and other 1 (10111111). This mask is bit representation of underscore character (‘_‘). The character ‘ch’ then AND with mask.
Example-
ch = ‘a’ (01100001)
mask = ‘_ ‘ (11011111)
ch & mask = ‘A’ (01000001)
Please refer Case conversion (Lower to Upper and Vice Versa) for details.
7) Count set bits in integer
CPP
int countSetBits(int x)
{
int count = 0;
while (x)
{
x &= (x-1);
count++;
}
return count;
}
Logic: This is Brian Kernighan’s algorithm.
8) Find log base 2 of 32 bit integer
CPP
int log2(int x)
{
int res = 0;
while (x >>= 1)
res++;
return res;
}
Logic: We right shift x repeatedly until it becomes 0, meanwhile we keep count on the shift operation. This count value is the log2(x).
9) Checking if given 32 bit integer is power of 2

CPP
int isPowerof2(int x)
{
return (x && !(x & x-1));
}
Logic: All the power of 2 have only single bit set e.g. 16 (00010000). If we minus 1 from this, all the bits from LSB to set bit get toggled, i.e., 16-1 = 15 (00001111). Now if we
AND x with (x-1) and the result is 0 then we can say that x is power of 2 otherwise not. We have to take extra care when x = 0.
Example
x = 16(000100000)
x – 1 = 15(00001111)
x & (x-1) = 0
so 16 is power of 2
Labels:

Comments

Post a Comment

Popular posts from this blog

How to create Annotation in Spring boot

 To create Custom Annotation in JAVA, @interface keyword is used. The annotation contains :  1. Retention :  @Retention ( RetentionPolicy . RUNTIME ) It specifies that annotation should be available at runtime. 2. Target :  @Target ({ ElementType . METHOD }) It specifies that the annotation can only be applied to method. The target cane be modified to:   @Target ({ ElementType . TYPE }) for class level annotation @Target ({ ElementType . FIELD }) for field level annotation @Retention ( RetentionPolicy . RUNTIME ) @Target ({ ElementType . FIELD }) public @ interface CustomAnnotation { String value () default "default value" ; } value attribute is defined with @ CustomAnnotation annotation. If you want to use the attribute in annotation. A single attribute value. Example : public class Books {           @CustomAnnotation(value = "myBook")     public void updateBookDetail() {         ...
Post a Comment
Read more

Kafka And Zookeeper SetUp

 Kafka And Zookeeper SetUp zookeeper download Link : https://www.apache.org/dyn/closer.lua/zookeeper/zookeeper-3.8.3/apache-zookeeper-3.8.3-bin.tar.gz Configuration: zoo.conf # The number of milliseconds of each tick tickTime =2000 # The number of ticks that the initial # synchronization phase can take initLimit =10 # The number of ticks that can pass between # sending a request and getting an acknowledgement syncLimit =5 # the directory where the snapshot is stored. # do not use /tmp for storage, /tmp here is just # example sakes. dataDir =/tmp/zookeeper # the port at which the clients will connect clientPort =2181 4 char whitelist in command arguments 4lw.commands.whitelist =* Start ZooKeeper Server $ bin/zkServer.sh start Check zookeeper status dheeraj.kumar@Dheeraj-Kumar bin % echo stat | nc localhost 2181 stat is 4 character whitelisted argument  Check Kafka running status : echo dump | nc localhost 2181 | grep broker Responsibility of Leader in Zookeeper: 1. Distrib...
Post a Comment
Read more

Cache Policy

Cache policies determine how data is stored and retrieved from a cache, which is a small and fast storage area that holds frequently accessed data to reduce the latency of accessing that data from a slower, larger, and more distant storage location, such as main memory or disk. Different cache policies are designed to optimize various aspects of cache performance, including hit rate, latency, and consistency. Here are some common types of cache policies: Least Recently Used (LRU): LRU is a commonly used cache replacement policy. It evicts the least recently accessed item when the cache is full. LRU keeps track of the order in which items were accessed and removes the item that has not been accessed for the longest time. First-In-First-Out (FIFO): FIFO is a simple cache replacement policy. It removes the oldest item from the cache when new data needs to be stored, regardless of how frequently the items have been accessed. Most Recently Used (MRU): MRU removes the most recently accessed ...
Post a Comment
Read more