Help, BitMask function :(

  • Thread starter Thread starter Andy
  • Start date Start date
A

Andy

Sigh... working on it for whole day and got no idea...

Basically I want to have a bitmask filtering function, I will throw in
3 parameters:

bitMaskValue - current bitmask value
filterValue - the value I want to see if its exist in "bitMaskValue"
BiggestValue - the maximum individual value can be exist

And I want it just to return true if the value exist, or false if not

So for example, I have 7 as "bitMaskValue", "filterValue" as 2 and
"BiggestValue" as 4... then it will return True... as 1 + 2 + 4 = 7

If I have 5 as "bitMaskValue", "filterValue" as 2 and "BiggestValue"
as 4... then it will return False... as 1 + 4 = 5... no "2"

I have come up the following be it just don't work :(

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean
' Filter "filterValue" from "bitMaskValue" and return true if
value
' BiggestValue = biggest individual BitMask value
Dim filed As Boolean = False
While bitMaskValue > 1 And BiggestValue > 0
If bitMaskValue >= BiggestValue And BiggestValue <>
filterValue Then
bitMaskValue = bitMaskValue - BiggestValue
End If
If BiggestValue = filterValue Then
filed = True
End If
BiggestValue = BiggestValue / 2
End While
If filed Then
Return bitMaskValue = filterValue
Else
Return bitMaskValue = 0
End If

End Function

If I have the maximum possible value (in this case, 7) then it's ok...
if I have a bit missing in between the function will fail... I have
tried so many approach but I just can't think through it... any help
would be appericiated.

Thanks in advance.
 
Some times it is better to build from the ground up. Here is some rough
spuedo-code with the obvious initial checks excluded.

Function SequentialBitMaskFilter(bitMask, biggestBit, filterMask)

<Obvious checks not included>

If filterMask = bitMask OR filterMask = 1 Then
Return True
End If

maskFound = False
nextBit = 1
bitBuilder = 1

Do While nextBit < biggestBit AND
bitBuilder < bitMask AND NOT maskFound
nextBit *= 2
bitBuilder += nextBit
If filterMask = nextBit OR
filterMask = bitBuilder Then
maskFound = True
ElseIf filterMask < nextBit Then
Exit Loop
End If
Loop

Return maskFound

End Function

***Important: Notice that the above only test for a sequential sum
filterMask. In other words it will catch filterMask values like;
1+2+4 or generally 1+2+4+...+2^m
However it will not catch filterMask values like;
1+8 (2 and 4 ommited) or generally
1+...+2^n +2^(n+x) +2^(n+x+1) +...+2^m
n<m, x>0, (n+x)<m
even though these filter mask do exist in a bitMask of 1+2+4+8 and
1+2+...+2^m. For this you need to take into account the combinations of n
bit positions choosing 1 bit to n bits for n in [1, m]. You can use the
above with a few modification in the loop to easily test for these cases.
You will also need to code a simple combinations function. I have not done
this here since your question does not seem to need to check non-sequential
sum filterMask. I just thought that you be aware of the limitations of the
solution.

--Robby
 
Andy said:
Sigh... working on it for whole day and got no idea...

Basically I want to have a bitmask filtering function, I will throw in
3 parameters:

bitMaskValue - current bitmask value
filterValue - the value I want to see if its exist in "bitMaskValue"
BiggestValue - the maximum individual value can be exist

And I want it just to return true if the value exist, or false if not

So for example, I have 7 as "bitMaskValue", "filterValue" as 2 and
"BiggestValue" as 4... then it will return True... as 1 + 2 + 4 = 7

If I have 5 as "bitMaskValue", "filterValue" as 2 and "BiggestValue"
as 4... then it will return False... as 1 + 4 = 5... no "2"

I have come up the following be it just don't work :(

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean
' Filter "filterValue" from "bitMaskValue" and return true if
value
' BiggestValue = biggest individual BitMask value
Dim filed As Boolean = False
While bitMaskValue > 1 And BiggestValue > 0
If bitMaskValue >= BiggestValue And BiggestValue <>
filterValue Then
bitMaskValue = bitMaskValue - BiggestValue
End If
If BiggestValue = filterValue Then
filed = True
End If
BiggestValue = BiggestValue / 2
End While
If filed Then
Return bitMaskValue = filterValue
Else
Return bitMaskValue = 0
End If

End Function

If I have the maximum possible value (in this case, 7) then it's ok...
if I have a bit missing in between the function will fail... I have
tried so many approach but I just can't think through it... any help
would be appericiated.

Thanks in advance.
Click to expand...

I may be missing the point somewhat but could you not use something like
this: -

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean

'***Checks to ensure sensible input omitted***

Dim result As Integer = bitMaskValue And filterValue
Return (result > 0 AndAlso result <= BiggestValue)

End Function

Regards,

Nick Hall
 
Actually, after a goods nights sleep this method is not the best. I came up
with a new one but Nick beat me to it.

--Robby

Robby said:
Some times it is better to build from the ground up. Here is some rough
spuedo-code with the obvious initial checks excluded.

Function SequentialBitMaskFilter(bitMask, biggestBit, filterMask)

<Obvious checks not included>

If filterMask = bitMask OR filterMask = 1 Then
Return True
End If

maskFound = False
nextBit = 1
bitBuilder = 1

Do While nextBit < biggestBit AND
bitBuilder < bitMask AND NOT maskFound
nextBit *= 2
bitBuilder += nextBit
If filterMask = nextBit OR
filterMask = bitBuilder Then
maskFound = True
ElseIf filterMask < nextBit Then
Exit Loop
End If
Loop

Return maskFound

End Function

***Important: Notice that the above only test for a sequential sum
filterMask. In other words it will catch filterMask values like;
1+2+4 or generally 1+2+4+...+2^m
However it will not catch filterMask values like;
1+8 (2 and 4 ommited) or generally
1+...+2^n +2^(n+x) +2^(n+x+1) +...+2^m
n<m, x>0, (n+x)<m
even though these filter mask do exist in a bitMask of 1+2+4+8 and
1+2+...+2^m. For this you need to take into account the combinations of
n bit positions choosing 1 bit to n bits for n in [1, m]. You can use the
above with a few modification in the loop to easily test for these cases.
You will also need to code a simple combinations function. I have not
done this here since your question does not seem to need to check
non-sequential sum filterMask. I just thought that you be aware of the
limitations of the solution.

--Robby



Andy said:
Sigh... working on it for whole day and got no idea...

Basically I want to have a bitmask filtering function, I will throw in
3 parameters:

bitMaskValue - current bitmask value
filterValue - the value I want to see if its exist in "bitMaskValue"
BiggestValue - the maximum individual value can be exist

And I want it just to return true if the value exist, or false if not

So for example, I have 7 as "bitMaskValue", "filterValue" as 2 and
"BiggestValue" as 4... then it will return True... as 1 + 2 + 4 = 7

If I have 5 as "bitMaskValue", "filterValue" as 2 and "BiggestValue"
as 4... then it will return False... as 1 + 4 = 5... no "2"

I have come up the following be it just don't work :(

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean
' Filter "filterValue" from "bitMaskValue" and return true if
value
' BiggestValue = biggest individual BitMask value
Dim filed As Boolean = False
While bitMaskValue > 1 And BiggestValue > 0
If bitMaskValue >= BiggestValue And BiggestValue <>
filterValue Then
bitMaskValue = bitMaskValue - BiggestValue
End If
If BiggestValue = filterValue Then
filed = True
End If
BiggestValue = BiggestValue / 2
End While
If filed Then
Return bitMaskValue = filterValue
Else
Return bitMaskValue = 0
End If

End Function

If I have the maximum possible value (in this case, 7) then it's ok...
if I have a bit missing in between the function will fail... I have
tried so many approach but I just can't think through it... any help
would be appericiated.

Thanks in advance.
Click to expand...
Click to expand...
 
Robby,

It's acutally the non-sequential sum filterMask checking is bugging
me. If it's just the sequence one it will just take me 2 mins because
it's easy.

Would you mind to fill me in on the non-sequential sum checking part
with what you have given me, please?

Thank you.


Andy

Robby said:
Some times it is better to build from the ground up. Here is some rough
spuedo-code with the obvious initial checks excluded.

Function SequentialBitMaskFilter(bitMask, biggestBit, filterMask)

<Obvious checks not included>

If filterMask = bitMask OR filterMask = 1 Then
Return True
End If

maskFound = False
nextBit = 1
bitBuilder = 1

Do While nextBit < biggestBit AND
bitBuilder < bitMask AND NOT maskFound
nextBit *= 2
bitBuilder += nextBit
If filterMask = nextBit OR
filterMask = bitBuilder Then
maskFound = True
ElseIf filterMask < nextBit Then
Exit Loop
End If
Loop

Return maskFound

End Function

***Important: Notice that the above only test for a sequential sum
filterMask. In other words it will catch filterMask values like;
1+2+4 or generally 1+2+4+...+2^m
However it will not catch filterMask values like;
1+8 (2 and 4 ommited) or generally
1+...+2^n +2^(n+x) +2^(n+x+1) +...+2^m
n<m, x>0, (n+x)<m
even though these filter mask do exist in a bitMask of 1+2+4+8 and
1+2+...+2^m. For this you need to take into account the combinations of n
bit positions choosing 1 bit to n bits for n in [1, m]. You can use the
above with a few modification in the loop to easily test for these cases.
You will also need to code a simple combinations function. I have not done
this here since your question does not seem to need to check non-sequential
sum filterMask. I just thought that you be aware of the limitations of the
solution.

--Robby



Andy said:
Sigh... working on it for whole day and got no idea...

Basically I want to have a bitmask filtering function, I will throw in
3 parameters:

bitMaskValue - current bitmask value
filterValue - the value I want to see if its exist in "bitMaskValue"
BiggestValue - the maximum individual value can be exist

And I want it just to return true if the value exist, or false if not

So for example, I have 7 as "bitMaskValue", "filterValue" as 2 and
"BiggestValue" as 4... then it will return True... as 1 + 2 + 4 = 7

If I have 5 as "bitMaskValue", "filterValue" as 2 and "BiggestValue"
as 4... then it will return False... as 1 + 4 = 5... no "2"

I have come up the following be it just don't work :(

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean
' Filter "filterValue" from "bitMaskValue" and return true if
value
' BiggestValue = biggest individual BitMask value
Dim filed As Boolean = False
While bitMaskValue > 1 And BiggestValue > 0
If bitMaskValue >= BiggestValue And BiggestValue <>
filterValue Then
bitMaskValue = bitMaskValue - BiggestValue
End If
If BiggestValue = filterValue Then
filed = True
End If
BiggestValue = BiggestValue / 2
End While
If filed Then
Return bitMaskValue = filterValue
Else
Return bitMaskValue = 0
End If

End Function

If I have the maximum possible value (in this case, 7) then it's ok...
if I have a bit missing in between the function will fail... I have
tried so many approach but I just can't think through it... any help
would be appericiated.

Thanks in advance.
Click to expand...
Click to expand...
 
Andy

You don't have to worry about the non-seqential if you use a bit operator
like Nick suggested.

What is weird about your post is the 'biggest bit' requirement. I'm not
certain that you need it. There is only one way to represent a number in
binary so 7 will always be {11100000} and 5 will always be {10100000}.
Therefore in these cases that you used as your examples specifiying the
biggest bit as 4 {00100000} is completely unessesary. This can be extended
to any number since it only has one binary representation there is no need
to try and validate that the biggiest bit will conform. It must conform or
the number will be a different number.

Why do you need to specify the biggest bit? Will your value of the biggest
bit ever differ from the most significant bit that defines your bit mask as
it perticular number?

--Robby

Andy said:
Robby,

It's acutally the non-sequential sum filterMask checking is bugging
me. If it's just the sequence one it will just take me 2 mins because
it's easy.

Would you mind to fill me in on the non-sequential sum checking part
with what you have given me, please?

Thank you.


Andy

Robby said:
Some times it is better to build from the ground up. Here is some rough
spuedo-code with the obvious initial checks excluded.

Function SequentialBitMaskFilter(bitMask, biggestBit, filterMask)

<Obvious checks not included>

If filterMask = bitMask OR filterMask = 1 Then
Return True
End If

maskFound = False
nextBit = 1
bitBuilder = 1

Do While nextBit < biggestBit AND
bitBuilder < bitMask AND NOT maskFound
nextBit *= 2
bitBuilder += nextBit
If filterMask = nextBit OR
filterMask = bitBuilder Then
maskFound = True
ElseIf filterMask < nextBit Then
Exit Loop
End If
Loop

Return maskFound

End Function

***Important: Notice that the above only test for a sequential sum
filterMask. In other words it will catch filterMask values like;
1+2+4 or generally 1+2+4+...+2^m
However it will not catch filterMask values like;
1+8 (2 and 4 ommited) or generally
1+...+2^n +2^(n+x) +2^(n+x+1) +...+2^m
n<m, x>0, (n+x)<m
even though these filter mask do exist in a bitMask of 1+2+4+8 and
1+2+...+2^m. For this you need to take into account the combinations of
n
bit positions choosing 1 bit to n bits for n in [1, m]. You can use the
above with a few modification in the loop to easily test for these cases.
You will also need to code a simple combinations function. I have not
done
this here since your question does not seem to need to check
non-sequential
sum filterMask. I just thought that you be aware of the limitations of
the
solution.

--Robby



Andy said:
Sigh... working on it for whole day and got no idea...

Basically I want to have a bitmask filtering function, I will throw in
3 parameters:

bitMaskValue - current bitmask value
filterValue - the value I want to see if its exist in "bitMaskValue"
BiggestValue - the maximum individual value can be exist

And I want it just to return true if the value exist, or false if not

So for example, I have 7 as "bitMaskValue", "filterValue" as 2 and
"BiggestValue" as 4... then it will return True... as 1 + 2 + 4 = 7

If I have 5 as "bitMaskValue", "filterValue" as 2 and "BiggestValue"
as 4... then it will return False... as 1 + 4 = 5... no "2"

I have come up the following be it just don't work :(

Private Function BitMaskFilter(ByVal bitMaskValue As Int32, ByVal
filterValue As Int32, ByVal BiggestValue As Int32) As Boolean
' Filter "filterValue" from "bitMaskValue" and return true if
value
' BiggestValue = biggest individual BitMask value
Dim filed As Boolean = False
While bitMaskValue > 1 And BiggestValue > 0
If bitMaskValue >= BiggestValue And BiggestValue <>
filterValue Then
bitMaskValue = bitMaskValue - BiggestValue
End If
If BiggestValue = filterValue Then
filed = True
End If
BiggestValue = BiggestValue / 2
End While
If filed Then
Return bitMaskValue = filterValue
Else
Return bitMaskValue = 0
End If

End Function

If I have the maximum possible value (in this case, 7) then it's ok...
if I have a bit missing in between the function will fail... I have
tried so many approach but I just can't think through it... any help
would be appericiated.

Thanks in advance.
Click to expand...
Click to expand...
Click to expand...
 
You must log in or register to reply here.

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Copy row contents based on contents 1
User Form 2
return value, exit function 4
hack that key validation. 1
System.Windows.Forms.KeyEventArgs 4
Create New RegistryKey 4
IP Subnet Calculator - Excel Function 1
Extending RichTextBox - Help Required 8

Back
Top