r*******n
发帖数: 51 | 1 有一个N位整数K，我想提出最高位或最低位的1，要求复杂度为O(1)。
log运算行不行啊？ | a******t
发帖数: 100 | 2
For the lowest 1, you can do :
N & (-N);
Here assumes - and & take O(1) time, which may not be true.
It seems you can not do for the most significant 1.
It is equivalent to compute log(N).
【在 r*******n 的大作中提到】
: 有一个N位整数K，我想提出最高位或最低位的1，要求复杂度为O(1)。
: log运算行不行啊？
| r*******n
发帖数: 51 | 3 Thank you sooooooooo much.
But what if I want to know the position of the lowest 1? I mean, for example,
I get 0100 and I want to know the 1 is located at 2th bit. How can I do that?
【在 a******t 的大作中提到】
:
: For the lowest 1, you can do :
: N & (-N);
: Here assumes - and & take O(1) time, which may not be true.
: It seems you can not do for the most significant 1.
: It is equivalent to compute log(N).
| a******t
发帖数: 100 | 4
I am not sure if you can do it in constant time.
A lg(n) algorithm is obvious, where n is number of bits in registers.
Just count how many 1's in (x - 1).
If you use popcount instruction in IA-64, it is constant time, from what
you see.
【在 r*******n 的大作中提到】
: Thank you sooooooooo much.
: But what if I want to know the position of the lowest 1? I mean, for example,
: I get 0100 and I want to know the 1 is located at 2th bit. How can I do that?
| n***n
发帖数: 15 | 5 You can do it in O(1). Search like "most significant 1" online or in an
algorithm / data structure textbook, it's a basic trick and a homework
exercise. For your original question, I am sure it should be 整数N
instead of N位整数.
example,
that?
【在 r*******n 的大作中提到】
: Thank you sooooooooo much.
: But what if I want to know the position of the lowest 1? I mean, for example,
: I get 0100 and I want to know the 1 is located at 2th bit. How can I do that?
| a******t
发帖数: 100 | 6
What's your solutions for "most significant 1" ?
He meant n-bit integer. Nothing wrong.
【在 n***n 的大作中提到】
: You can do it in O(1). Search like "most significant 1" online or in an
: algorithm / data structure textbook, it's a basic trick and a homework
: exercise. For your original question, I am sure it should be 整数N
: instead of N位整数.
:
: example,
: that?
| r*******n
发帖数: 51 | 7 Suppose we have an integer K with maximal N bits. I searched "most significant
1" online and found one called "Next Largest Power of 2". Unfortunately, I
doublecheck the code and find the complexity to do it is O(N) instead of O(1).
Are you sure that you can do it in O(1)?
【在 n***n 的大作中提到】
: You can do it in O(1). Search like "most significant 1" online or in an
: algorithm / data structure textbook, it's a basic trick and a homework
: exercise. For your original question, I am sure it should be 整数N
: instead of N位整数.
:
: example,
: that?
| n***n
发帖数: 15 | 8 I guess that's it. So we believe that if we have a bit machine, then for any
整数N (with logN digits, of course) we can find the most significant 1 in
constant time. Your problem however, as you described, is that we have a
(0,1) string of length N, with N being the input size, and we want to find
the first 1. I don't think we can do it in any time less than N because we
need at least read the input string.
如果是一道题,八成是笔误或看错题了.如果是你真的自己需要处理那么巨大的整数,
也就是把字串长度N作为input size,大概只能一位一位地读.
significant
O(1).
【在 r*******n 的大作中提到】
: Suppose we have an integer K with maximal N bits. I searched "most significant
: 1" online and found one called "Next Largest Power of 2". Unfortunately, I
: doublecheck the code and find the complexity to do it is O(N) instead of O(1).
: Are you sure that you can do it in O(1)?
| n***n
发帖数: 15 | 9 事实上没有人会把一个N长的(0,1)串叫做一个整数.
do
【在 n***n 的大作中提到】
: I guess that's it. So we believe that if we have a bit machine, then for any
: 整数N (with logN digits, of course) we can find the most significant 1 in
: constant time. Your problem however, as you described, is that we have a
: (0,1) string of length N, with N being the input size, and we want to find
: the first 1. I don't think we can do it in any time less than N because we
: need at least read the input string.
: 如果是一道题,八成是笔误或看错题了.如果是你真的自己需要处理那么巨大的整数,
: 也就是把字串长度N作为input size,大概只能一位一位地读.
:
: significant
| r*******n
发帖数: 51 | 10 I think I mentioned that it is an integer with maximal N bits. For 64-bit
operation system, N is 64 and the unsigned integer is between 0-(2^N-1).
Please let me emphasize again. It is not a bit string.
do
【在 n***n 的大作中提到】
: I guess that's it. So we believe that if we have a bit machine, then for any
: 整数N (with logN digits, of course) we can find the most significant 1 in
: constant time. Your problem however, as you described, is that we have a
: (0,1) string of length N, with N being the input size, and we want to find
: the first 1. I don't think we can do it in any time less than N because we
: need at least read the input string.
: 如果是一道题,八成是笔误或看错题了.如果是你真的自己需要处理那么巨大的整数,
: 也就是把字串长度N作为input size,大概只能一位一位地读.
:
: significant
| | | n***n
发帖数: 15 | 11 Then you certainly do it in O(1) time. That is even taken for granted in alg.
design.
any
I
an
【在 r*******n 的大作中提到】
: I think I mentioned that it is an integer with maximal N bits. For 64-bit
: operation system, N is 64 and the unsigned integer is between 0-(2^N-1).
: Please let me emphasize again. It is not a bit string.
:
: do
| r*******n
发帖数: 51 | 12 But how? Could you please give us some details? I think the least complexity
to find the position of the highest 1 is binary searching that needs O(log N).
alg.
in
find
we
,
Unfortunately,
of
homework
for
I
【在 n***n 的大作中提到】
: Then you certainly do it in O(1) time. That is even taken for granted in alg.
: design.
:
: any
: I
: an
| i*******g
发帖数: 168 | 13 what do you mean by "提出最高位或最低位的1"? find the index (location)?
if so, it's impossible to do it in O(1). lg(n) is ok.
【在 r*******n 的大作中提到】
: But how? Could you please give us some details? I think the least complexity
: to find the position of the highest 1 is binary searching that needs O(log N).
:
: alg.
: in
: find
: we
: ,
: Unfortunately,
: of
| a******t
发帖数: 100 | 14
It is not the index in the original post, I think.
Take an 8-bit integer as an example,
01001100
The least significant 1 would be:
00000100
And the most significant 1 would be:
01000000
Doing x & (-x) will generate the least significant 1.
Here, we assume - and & operations take O(1) time, which is true
on most processors. For instance, no matter it is an 8-bit, 16-bit,
32-bit, or 64-bit processor, each of - and & takes one cycle to finish.
Of course, it is not for free; the complexity of hard
【在 i*******g 的大作中提到】
: what do you mean by "提出最高位或最低位的1"? find the index (location)?
: if so, it's impossible to do it in O(1). lg(n) is ok.
| r*******n
发帖数: 51 | 15 Thanks million times!
【在 a******t 的大作中提到】
:
: It is not the index in the original post, I think.
: Take an 8-bit integer as an example,
: 01001100
: The least significant 1 would be:
: 00000100
: And the most significant 1 would be:
: 01000000
: Doing x & (-x) will generate the least significant 1.
: Here, we assume - and & operations take O(1) time, which is true
| i*******g
发帖数: 168 | 16 I guess it depends on what's the "basic operation" here.
If the complexity is counted based on "bit operation", then
"Doing x & (-x)" will never be a O(1) step.
Anyway, think of if "x" is 10 million bytes long, can you still
take "Doing x & (-x)" as a constant?
【在 a******t 的大作中提到】
:
: It is not the index in the original post, I think.
: Take an 8-bit integer as an example,
: 01001100
: The least significant 1 would be:
: 00000100
: And the most significant 1 would be:
: 01000000
: Doing x & (-x) will generate the least significant 1.
: Here, we assume - and & operations take O(1) time, which is true
| a******t
发帖数: 100 | 17
That's the assumption. we assume each instruction take O(1) time.
In sorting algorithms, one assumption is a
comparisoin takes O(1) time, which is not true if you can only access
a bit each time.
again, assumption.
【在 i*******g 的大作中提到】
: I guess it depends on what's the "basic operation" here.
: If the complexity is counted based on "bit operation", then
: "Doing x & (-x)" will never be a O(1) step.
: Anyway, think of if "x" is 10 million bytes long, can you still
: take "Doing x & (-x)" as a constant?
| i*******g
发帖数: 168 | 18 I suspect the assumption isn't valid for this problem, because,
otherwise, there will be no difference between an N位整数 and an
N^2位整数. The input size is measured by "digit" here.
For sorting problem, the input size "N" is measured with "the number of
elements".
total
【在 a******t 的大作中提到】
:
: That's the assumption. we assume each instruction take O(1) time.
: In sorting algorithms, one assumption is a
: comparisoin takes O(1) time, which is not true if you can only access
: a bit each time.
: again, assumption.
| r*******n
发帖数: 51 | 19 I agree with you because we can assume that the x can't be larger than what
the register can load. The complexity of operation x&(-x) should be somehow
constant, I guess, because the operation & should be done in one clock cycle
but -x might depend on bit length. However, it doesn't matter because we treat
sub operation as a O(1) operation. In this sense, we can say x&(-x) is a O(1)
operation.
I am now just wondering that if I want to use popcount, the only way to do it
is using assembly, right?
【在 a******t 的大作中提到】
:
: That's the assumption. we assume each instruction take O(1) time.
: In sorting algorithms, one assumption is a
: comparisoin takes O(1) time, which is not true if you can only access
: a bit each time.
: again, assumption.
| i*******g
发帖数: 168 | 20 "x won't be bigger than, say 64 bits"? then everything will be O(1).
Just count, from left and right to figure out who are the first & last "1"s.
treat
O(1)
it
C/C++.
finish.
【在 r*******n 的大作中提到】
: I agree with you because we can assume that the x can't be larger than what
: the register can load. The complexity of operation x&(-x) should be somehow
: constant, I guess, because the operation & should be done in one clock cycle
: but -x might depend on bit length. However, it doesn't matter because we treat
: sub operation as a O(1) operation. In this sense, we can say x&(-x) is a O(1)
: operation.
: I am now just wondering that if I want to use popcount, the only way to do it
: is using assembly, right?
| r*******n
发帖数: 51 | 21 Yes, you can do that but the complexity is, unfortunately, not O(1) because
the counting circle depends on N.
what
somehow
cycle
【在 i*******g 的大作中提到】
: "x won't be bigger than, say 64 bits"? then everything will be O(1).
: Just count, from left and right to figure out who are the first & last "1"s.
:
: treat
: O(1)
: it
: C/C++.
: finish.
| f*****r
发帖数: 229 | 22
treat
O(1)
it
C/C++.
Let us get the Linux version of bitcount:
/*
41 * hweightN: returns the hamming weight (i.e. the number
42 * of bits set) of a N-bit word
43 */
44
45 static inline unsigned int generic_hweight32(unsigned int w)
46 {
47 unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
48 res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
49 res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
50 res = (res & 0x00FF00FF) + ((res >> 8) & 0x0
【在 r*******n 的大作中提到】
: I agree with you because we can assume that the x can't be larger than what
: the register can load. The complexity of operation x&(-x) should be somehow
: constant, I guess, because the operation & should be done in one clock cycle
: but -x might depend on bit length. However, it doesn't matter because we treat
: sub operation as a O(1) operation. In this sense, we can say x&(-x) is a O(1)
: operation.
: I am now just wondering that if I want to use popcount, the only way to do it
: is using assembly, right?
|
|
