## DEV Community is a community of 905,285 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Huy Do

Posted on

# Bit Manipulation

### Get Bit

This method shifts the relevant bit to the zeroth position. Then we perform AND operation with one which has bit pattern like 0001. This clears all bits from the original number except the relevant one. If the relevant bit is one, the result is 1, otherwise the result is 0.

### Set Bit

This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Then we perform OR operation that sets specific bit into 1 but it does not affect on other bits of the number.

### Clear Bit

This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Than it inverts this mask to get the number that looks like 11011. Then AND operation is being applied to both the number and the mask. That operation unsets the bit.

### Update Bit

This method is a combination of "Clear Bit" and "Set Bit" methods.

### isEven

This method determines if the number provided is even. It is based on the fact that odd numbers have their last right bit to be set to 1.

``````Number: 5 = 0b0101
isEven: false

Number: 4 = 0b0100
isEven: true
``````

### isPositive

This method determines if the number is positive. It is based on the fact that all positive numbers have their leftmost bit to be set to 0. However, if the number provided is zero or negative zero, it should still return false.

``````Number: 1 = 0b0001
isPositive: true

Number: -1 = -0b0001
isPositive: false
``````

### Multiply By Two

This method shifts original number by one bit to the left. Thus all binary number components (powers of two) are being multiplying by two and thus the number itself is being multiplied by two.

``````Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b1010 = 10
Powers of two: 2^3 + 0 + 2^1 + 0
``````

### Divide By Two

This method shifts original number by one bit to the right. Thus all binary number components (powers of two) are being divided by two and thus the number itself is being divided by two without remainder.

``````Before the shift
Number: 0b0101 = 5
Powers of two: 0 + 2^2 + 0 + 2^0

After the shift
Number: 0b0010 = 2
Powers of two: 0 + 0 + 2^1 + 0
``````

### Switch Sign

This method make positive numbers to be negative and backwards. To do so it uses "Twos Complement" approach which does it by inverting all of the bits of the number and adding 1 to it.

``````1101 -3
1110 -2
1111 -1
0000  0
0001  1
0010  2
0011  3
``````

### Multiply Two Signed Numbers

This method multiplies two signed integer numbers using bitwise operators. This method is based on the following facts:

``````a * b can be written in the below formats:
0                     if a is zero or b is zero or both a and b are zeroes
2a * (b/2)            if b is even
2a * (b - 1)/2 + a    if b is odd and positive
2a * (b + 1)/2 - a    if b is odd and negative
``````

The advantage of this approach is that in each recursive step one of the operands reduces to half its original value. Hence, the run time complexity is O(log(b)) where b is the operand that reduces to half on each recursive step.

# References

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/bits
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://practicaldev-herokuapp-com.global.ssl.fastly.net/huyddo/bit-manipulation-50ad", "fetch_time": 1660449023000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2022-33/segments/1659882571993.68/warc/CC-MAIN-20220814022847-20220814052847-00166.warc.gz", "warc_record_offset": 423331539, "warc_record_length": 27840, "token_count": 933, "char_count": 3360, "score": 3.765625, "int_score": 4, "crawl": "CC-MAIN-2022-33", "snapshot_type": "longest", "language": "en", "language_score": 0.902004063129425, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00049-of-00064.parquet"}