0

I am studying about bitwise logical operations (AND, OR, etc.). For example.

15 AND 24 can be calculated as follow.

  1. convert given numbers into binary form.

01111 AND 11000

  1. Perform bitwise AND operation on each bit from both the numbers.

= 01000

  1. convert binary to decimal form.

8

I want to know,

  1. Is there a direct way (without convert into the binary form) to get the result of this operation? If not please do tell what is the optimal way available to get the result. I need to do this for very large numbers up to 170141183460469231731687303715884105728 or beyond this.

  2. I am trying to implement it in C, I can't store an integer greater than 18446744073709551615 in C, So I was wondering how operations on large numbers are achieved given that we can't store these numbers directly.

Is there any algorithm that takes chunks of these numbers and performs these operations. For example

0170 1411 8346 0469 2317 3168 7303 7158 8410 5728
&
1321 3221 3654 5646 5646 6546 6489 9873 9765 9721
-------------------------------------------------
result = very large number

Is there any online resource that I can use to get more understanding on this?

confucius_007
  • 186
  • 1
  • 15
  • 1
    No, there is no more direct way. The most efficient way is language specific, but most languages provide the most efficient methods to implement the bitwise operators. – President James K. Polk Aug 11 '20 at 13:31
  • 1
    A lot of current languages implement `AND` on integers as `a & b`. A vertical bar is often used for `OR`: `a | b` . Note that your maximum value is 127 bit long, so you probably need a special extra long integer data type. Languages such as Python support integers of unlimited size, so you can directly call `a & b` on such integers. – JohanC Aug 11 '20 at 14:25
  • 2
    @JohanC well, you could of course hide behind language constructs, but internal logic is still binary based – Severin Pappadeux Aug 11 '20 at 15:29
  • Please keep in mind that you should have the computer store its values in binary, so that the computer can work directly on the values. Conversion to and from decimal is then only ever needed when interfacing with humans. DO NOT store the values as decimal, then convert from decimal to binary before the bitwise logical operation, and then convert back to decimal for storage. I have seen someone do that, and watching that kind of inefficiency is painful. – ndim Aug 19 '20 at 06:10

1 Answers1

2

There is no direct way to get the result - you have to convert to binary.

Luckily, computers are pretty good a converting decimal numbers to binary. They use binary all the time: once you put a number in a computer, the first thing it does is convert it into binary. Similarly, when you print the results, the binary number is automatically converted into decimal.

Here is how you can compute the bitwise logical AND in Python for example:

print(15 & 24)
# prints: 8

See how you didn't have to do anything to convert the numbers to binary yourself, or convert the result to decimal? The programming language and its libraries did it all for you.

It works for very large numbers too:

print(123456789012345678901234567890 & 987654321987654321987654321)
# prints: 657693129655407100634333840

Update: The C language does not have arbitrary large integer type. The data types available vary by target platform and the compiler: if you're targeting a 64 bit CPU you can use up to 128 bit integers which gets you covered up to 170141183460469231731687303715884105728. See Is there a 128 bit integer in gcc?

If you want to go beyond that that (or you're targeting other architectures) you'll need a library that implements "arbitrary precision arithmetic". There are several options available. GNU GMP is one of the best known. Cryptographic libraries such as OpenSSL also come with functions to do calculations with arbitrary large integers.

With GMP, you would use the mpz_and function for the "bitwise and" operation of two numbers.

Joni
  • 108,737
  • 14
  • 143
  • 193