Time complexity in Bitwise questions

#1

https://codeforces.com/problemset/problem/1395/C

I have completed the question. I have a doubt in the time complexity of the problem. I saw the tutorial and found out the time complexity of the problem. This is the tutorial:

“Suppose the answer is A. Thus for all i (1≤i≤n), ci|A=A
Since ai,bi<29, we can enumerate all integers from 0 to 29−1, and check if there exists j for each i that (ai&bj)|A=A . The minimum of them will be the answer.
The time complexity is O(2^9 * n * 2).”

My doubt is the time complexity of bitwise and operation is not considered. If it was considered then the time complexity should be O(2^9 * n * 2 * 9 ). Then it will cross 10**7. Then it should be TLE right? Is bitwise And operation considered O(1).

#2

Yes time complexity of bitwise operations is O(1). They are considered faster than our regular operations. This is why it is suggested to check odd numbers by if(n&1) and not by if(n%2).

#3

So even if the the number is 218 or 2180 we can completely ignore the time taken on by bitwise opeartions on these numbers??

#4

It’s 218 and 2180

#5

2^18 and 2^180…

#6

Yes. It’s a constant time operation for all. And it is not possible to input numbers greater than 10^18 in C++.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.