CODEWITHSUNDEEP
javaoperatorstime-complexity
Anju Rawat
Anju Rawat

Reputation: 11

What is time complexity of bitwise & operator in java?

I want to know what is bitwise & operator time complexity in java and how to reduce it using alternative methods if any. Thanks in advance!!

Upvotes: 1

Views: 2359

Answers (3)

Peter Lawrey
Peter Lawrey

Reputation: 533530

Typically, the time complexity of & operations is O(n) where n is the number of 32-bit values or 64-bit values depending on the JVM.

For a single int value, the contents don't matter.

10^5 is length of array

In this case, the time will be proportional to length of the array.

The fastest way is to use long values and store 64-bits in each element.

no alternative from the user side to reduce this operation time complexity?

An & operation of two int values is one of the fastest operations a computer can do and typically takes 1 clock cycle i.e. << 1 ns. This is only a problem if you are doing a lot of them.

Upvotes: 1

chrylis -cautiouslyoptimistic-
chrylis -cautiouslyoptimistic-

Reputation: 77187

The Java bitwise operators operate on primitive operands and are each implemented using a pair of JVM bytecode instructions. Using & as an example, those instructions are iand for int and land for long. (In the JVM, the basic word size is 32 bits, and shorter integer types are theoretically stored as 32 bits.) The JVMS does not specify the time complexity of these instructions, but in any sane implementation they'll be implemented using the CPU's bitwise instructions, and so & on any particular data type is of constant time regardless of the operands' contents.

Upvotes: 3

ssaa
ssaa

Reputation: 1112

Bit operations are fast and can be used in optimizing time complexity. Some common bit operators are: NOT ( ~ ): Bitwise NOT is an unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa. Bitwise NOT is nothing but simply the one's complement of a number.

Upvotes: 0

Related Questions