CODEWITHSUNDEEP
stringalgorithmbitwise-operators
zubergu
zubergu

Reputation: 3706

Bitwise operations clarification on some cases

I'm asked to use bitwise operators on char array(binary strings). What should be the output of:

a) ~111; should the output string be 000, 1000 or something different?

b) 1010 (operator) 100; is the output the same as 1010 (operator) 0100, making those strings even with leading 0's will always work or is there a test case I am missing?

Upvotes: 2

Views: 148

Answers (2)

Ilmari Karonen
Ilmari Karonen

Reputation: 50338

One consistent way to implement bitwise operations, including negation, on arbitrary-length bitstrings is to:

  1. assume that all "normal" bitstrings implicitly have an infinite number of leading zero bits in front of them, and
  2. extend the space of bitstrings you're working with to also include "negative" bitstrings that have an infinite number of one bits in front of them.

Thus, for example ~111 = ...1000, where the ...1 stands for the infinite sequence of 1-bits.

You can check for yourself that this system will satisfy all the usual rules of Boolean algebra, such as De Morgan's laws:

~( ~111 | ~1010 ) = ~( ...1000 | ...10101 ) = ~...11101 =   10 = 111 & 1010
~( ~111 & ~1010 ) = ~( ...1000 & ...10101 ) = ~...10000 = 1111 = 111 | 1010

In particular, if you're using your arbitrary-length bitstrings to represent integers in base 2 (i.e. 1 = 1, 10 = 2, 11 = 3, etc.), then the "negative bitstrings" naturally correspond to the negative numbers (e.g. ...1 = ~0 = −1, ...10 = ~1 = −2, ...101 = ~10 = −3, etc.) in generalized two's complement representation. Notably, this representation satisfies the general two's complement law that ~x = −x − 1.

Upvotes: 0

Sysyphus
Sysyphus

Reputation: 1051

~111 = 000

~0111 = 1000

Leading zeroes are important, because bitwise operations operate on each input bit.

Upvotes: 3

Related Questions