Logical operation / bit operation 0
Yes.
and AND
Returns 1 only if both x and y are 1. It is the description of x & y in the source code. It seems that x ・ y and x & y may be written in some explanations and problem sentences.
or OR
Returns 1 if at least one of x and y is 1. In the source code, it is the description of x | y. It seems that x + y may be written in some explanations and problem sentences.
xor · Exclusive OR
Returns 1 if only one of x and y is 1. It will be the description of x ^ y in the source code.
not / denial
It's flipped. It is described as ~ x in the source code.
Bit operation.py
x=7 #0111 in binary notation
y=11 #1011 in binary notation
#Logical AND
x&Since y is the 1st and 2nd digits in which 1 is set in both decimal notation, it is 3 in decimal.
#Logical sum
x|y is 15 in decimal notation because 1 is set in either or both of the 1st to 4th digits in decimal notation.
#Exclusive OR
x^y is in decimal notation, and only one of them has 1 in the 3rd and 4th digits, so it is 12 in decimal notation.
#denial
~x is a bit inverted and 1 stands in the 4th digit?In decimal-The code is also inverted with 8.
Yes, x = 7 is 0111, y = 11 is 1011, masked by OR, and it becomes 1111, and the value of 15 in decimal number comes out. I was thinking about what kind of work it would do to utilize it in the morning, and I came up with an example that it was probably like this.
I wonder if this is how to write it when using it for other problems.py
#Bitwise for loop template I wrote in a previous article?
youso =Number of elements given(Number of colors and knapsack)
seigen =You can choose up to 2 colors and weight 10 or less
max_value= -1
#Apparently the outermost range(1<<Element count)It's like writing in.
for all in range(1<<youso):
#Set the initial value of weight and value that comes out of each combination to 0
sum_weight = 0
sum_value = 0
#A little unknown element number loop
for i in range(youso):
#Another method of bit checking. It seems. .. ..
#Bit is standing(1)If you decide that you are using it, you are not standing(0)Then it is judged that it is not used. .. ..
if (all>>i & 1):
#Add the weight and value of the element determined to be in use
sum_weight += weight[[i]
sum_value += value[i]
if sum_weight<=W:
#First time max_value is-Since it is 1, sum_The value of value is assigned.
#From the second time onward, the larger number is max_It seems to be assigned to value.
max_value = max(max_value,sum_value)
print max_value
I heard that there is a high school girl who works part-time with me and Naka at a convenience store. Neither I nor Naka-chan have a weekly work schedule yet. Then, the logical sum counts how many combinations one or both of them go to work. All combinations are me (going to work, holidays) Naka-chan (going to work, holidays), 4 combinations in 7 days, 16384.
Naka-chan and part-time job.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import sys
import io
import re
import math
####Memory usage and operating time check preparation
from guppy import hpy
import time
start = time.clock()
h = hpy()
####Up to here
#If the bit is standing, go to work, if not, it is a holiday.
#My maximum number of working days is only 7 days a week.
i=7
#Maximum number of working days for Naka-chan(ry
n=7
#If either I or Naka-chan, or both, are at work, the counter
cnt=0
for x in xrange(1<<i):
for y in xrange(1<<n):
#x|If y is 127, the condition is satisfied.
if x|y==127:
cnt+=1
print (cnt)
####Memory usage and operating time output
end = time.clock()
print (h.heap())
print (end - start)
i and n are added one by one, so what is the state when n is 48, for example?
When the number is 48, the bits are set in 4 and 5 from the right, so the information that Tuesday and Wednesday are going to work is established. When all the bits from 0th to 6th are set, it becomes 127, so the condition is judged by 127 of the logical sum of x | y. There are 3 combinations and 2187 in 7 days that either I or Naka-chan or both will go to work.
Well, what should I say? .. .. If I read it properly, it was written carefully, but my brain wasn't enough. Reference Diagnostician's TopCoder brute force feature for beginners http://d.hatena.ne.jp/shindannin/20111202/1322833089
Bit shift
Shift to the left
x = 1 << 7 #x is 128 In the above case, 1 is shifted to the left 7 times, so it is 10000000 in binary notation.
Shift to the right
x = 1 >> 7 #x is 0 In the above case, 1 will not stand in the doko, so it will be 0 (probably). x = 7 >> 1 #x is 3 In the above case, 7 is shifted to the right once by shifting 111 in decimal notation, so it becomes 011 and it becomes 3 in decimal notation.
Yes. I've been using it for a long time with a sense of incongruity, and the loop of 1 << elements is also 7 days, so 1 << 7
python
I've been looping 128 times, but since it starts at 0, the last value in the loop was 1111111. ..
#### Postscript Note Assuming that the number is positive. .. .. ..
[http://codeforces.com/contest/76/problem/D](http://codeforces.com/contest/76/problem/D)
Additional notes to become more familiar with bit operations from the above problems
-Two numbers, A and B, are given.
・ A = X + Y (four arithmetic operations, not logical operations)
・ B = X ^ Y (xor of logical operation, exclusive OR)
In logical operations, the larger number, 1111 ..., is never exceeded.
When e.g 142 is displayed in bits, '0b10001110' with positive / negative display at the beginning and '10001110' without display.
The number in which this is filled with the maximum 1 is '0b11111111' or '11111111'. 255 in decimal. Since there is no carry-up, it will never be larger than the number filled with 1.
The sum of the four arithmetic operations and the result of xor may be equal, but there is no case where xor is larger (probably). ..
The pair that is expected to have a larger xor result is a pair that does not overlap each other where the bits pass.
e.g. The xor of a pair of 111 and 111 (7 in decimal) in decimal is 000 (isn't it?).
Pairs that do not overlap 1 that maximizes are 101 and 010 (decimal 5 and 2) pairs are 111 in decimal notation and 7 in decimal notation.
Therefore, if the location of 1 overlaps, the result of xor will be smaller than the result of the sum of the four arithmetic operations because there is no carry.
It seems to be proved because the result of the pair where the place of 1 where the result of xor is expected to be maximized (more efficiently?) Does not overlap is also equal to the result of the sum of the four arithmetic operations.
Practiced operations that I don't know how to use
#### **`e.`**
```python
#As an example n=142
>>> bin(n)
'0b10001110'
>>> bin(n)[2:]
'10001110'
#Such a state
#len -Maximum value with 1-bit shift
>>> (1<<len(bin(n)[2:]))-1
255
#Also bin, everything becomes 1
>>> bin((1<<len(bin(n)[2:]))-1)
'0b11111111'
>>> bin((1<<len(bin(n)[2:]))-1)[2:]
'11111111'
#When xoring, it seems that it is shifted because the leading 0 disappears,
#0 when viewed from the right,1 inversion
>>> bin(n^255)
'0b1110001'
>>> bin(n^255)[2:]
'1110001'
2013/11/01 22:18 We have made minor corrections and additions to Naka-chan. 2013/11/03 27:50 Added information about bit shift. 2014/03/04 23:16 Added that I confirmed a little. I can't understand the toco that seems to be useful.