Author |
Topic: bitwise operations questions (Read 818 times) |
|
meiro
Newbie
Posts: 3
|
 |
bitwise operations questions
« on: May 1st, 2007, 7:15am » |
 Quote  Modify
|
question #1
how do i find the i'th set-on bit in 32bit integer
(i.e. the index [0..31] of the i;th bit which set to one
for example
input = 01111000011010
get_i'th_item(5) == 9
question #2
given two 32 bit integer m,n how do i find if m is contains in the n (i.e. bit x is 1 in m should also be 1 n)
result = TRUE iff
for each in m (value(m, index) => value(n,index) )
for example
m = 00011000
n = 00111001
is_contains_in(m,n) = TRUE
m = 00011010
n = 00111001
is_contains_in(m,n) = FALSE
question #3
same as #2 for disjoint
BTW
I need very very fast algorithm
|
|
 IP Logged |
|
|
|
meiro
Newbie
Posts: 3
|
|
Re: bitwise operations questions
« Reply #1 on: May 1st, 2007, 7:26am » |
Quote Modify
|
oops
the answer to question #2 is very simple
result = (m & n == m)
please ignore question #2
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: bitwise operations questions
« Reply #2 on: May 1st, 2007, 7:37am » |
Quote Modify
|
#1: There is a way to count the number of 1's in an n-bit integer in O(log n) time by adding first each bit to its neighbor, then each 2 bits, then each 4 bits, etc. By keeping the intermediate results in O(log n) space, it should be possible to conduct a binary search for the i-th set bit in O(log n) time, giving an algorithm that is O(log n) in both time and space.
#3: I don't understand what you're asking. Do you want to know if m and n have no 1-bits in common? If so it's result = (m & ~n == m).
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
meiro
Newbie
Posts: 3
|
|
Re: bitwise operations questions
« Reply #3 on: May 1st, 2007, 8:07am » |
Quote Modify
|
please also ignore question #3 (a stupid question  )
sorry, but I'm not sure that I understood yours answer
can U add a code example (or pseudo code)
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: bitwise operations questions
« Reply #4 on: May 1st, 2007, 8:32am » |
Quote Modify
|
Sure, I'll walk through the example you gave (but the answer is 10, not 9):
input = 0001111000011010 (16 bits)
i = 5
First step -- count the 1 bits, keeping intermediate results:
t0 = input ("sum" of each bit)
t1 = (t0 & 0101010101010101) + ((t0 & 1010101010101010) >> 1) = 00 01 10 01 00 01 01 01 (sums of each 2 bits)
t2 = (t1 & 0011001100110011) + ((t1 & 1100110011001100) >> 2) = 0001 0011 0001 0010 (sums of each 4 bits)
t3 = (t2 & 0000111100001111) + ((t2 & 1111000011110000) >> 4) = 00000100 00000011 (sums of each 8 bits)
t4 = (t3 & 0000000011111111) + ((t3 & 1111111100000000) >> 8) = 0000000000000111 (sum of all 16 bits)
Second step -- binary search for the result:
- sum of bits 0-15 = 7 (from t4), so the 5th set bit lies in bits 0-15 (otherwise there would be no answer)
- sum of bits 0-7 = 3 (from t3), so the 5th set bit lies in bits 8-15
- sum of bits 8-11 = 3 (from t2) for a total of 6 in bits 0-11, so the 5th set bit lies in bits 8-11
- sum of bits 8-9 = 1 (from t1) for a total of 4 in bits 0-9, so the 5th set bit lies in bits 10-11
- "sum" of bit 10 = 1 (from t0) for a total of 5 in bits 0-10, so the 5th set bit is bit 10.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print