假设有一个192.168.54.0/24网络，如何快速分配一个可用ip，查找，添加，删除
192.168.54.0/24 可以使用 192.168.54.1-162.168.54.255 范围的ip，那么，就可以使用256个bit来表示某个ip是否已经被使用，在C#中，可以使用4个ulong来表示，于是
示例
C#
class FindIPTest
{
public ulong[] array = new ulong[4] { ulong.MaxValue, ulong.MaxValue, ulong.MaxValue, 0 };
/// <summary>
/// 查找网段内可用ip(/24)
/// </summary>
/// <param name="array">缓存数组</param>
/// <param name="value">找到的值</param>
/// <returns></returns>
/// <exception cref="Exception">array length must be 4</exception>
public bool Find(ulong[] array, out byte value)
{
value = 0;
if (array.Length != 4) throw new Exception("array length must be 4");
//排除 .1 .255 .256
array[0] |= 0b1;
array[3] |= (ulong)0b11 << 62;
if (array[0] < ulong.MaxValue) value = Find(array[0], 0);
else if (array[1] < ulong.MaxValue) value = Find(array[1], 1);
else if (array[2] < ulong.MaxValue) value = Find(array[2], 2);
else if (array[3] < ulong.MaxValue) value = Find(array[3], 3);
return value > 0;
}
private byte Find(ulong group, byte index)
{
byte value = (byte)(index * 64);
//每次对半开，也可以循环，循环稍微会慢3-4ns，常量值快一点
ulong _group = (group & uint.MaxValue);
if (_group >= uint.MaxValue) { _group = group >> 32; value += 32; }
group = _group;
_group = (group & ushort.MaxValue);
if (_group >= ushort.MaxValue) { _group = group >> 16; value += 16; }
group = _group;
_group = (group & byte.MaxValue);
if (_group >= byte.MaxValue) { _group = group >> 8; value += 8; }
group = _group;
_group = (group & 0b1111);
if (_group >= 0b1111) { _group = group >> 4; value += 4; }
group = _group;
_group = (group & 0b11);
if (_group >= 0b11) { _group = group >> 2; value += 2; }
group = _group;
_group = (group & 0b1);
if (_group >= 0b1) { value += 1; }
value += 1;
return value;
}
/// <summary>
/// 是否存在一个ip
/// </summary>
/// <param name="group"></param>
/// <param name="value"></param>
/// <returns></returns>
/// <exception cref="Exception"></exception>
public bool Exists(ulong[] array, byte value)
{
if (array.Length != 4) throw new Exception("array length must be 4");
int arrayIndex = value / 64;
int length = value - arrayIndex * 64;
return (array[arrayIndex] >> (length - 1) & 1) == 1;
}
/// <summary>
/// 将一个ip(/24)设为已使用
/// </summary>
/// <param name="array">缓存数组</param>
/// <param name="value">值</param>
public void Add(ulong[] array, byte value)
{
if (array.Length != 4) throw new Exception("array length must be 4");
int arrayIndex = value / 64;
int length = value - arrayIndex * 64;
array[arrayIndex] |= (ulong)1 << (length - 1);
}
/// <summary>
/// 删除一个ip(/24),设为未使用
/// </summary>
/// <param name="array"></param>
/// <param name="value"></param>
/// <exception cref="Exception"></exception>
public void Delete(ulong[] array, byte value)
{
if (array.Length != 4) throw new Exception("array length must be 4");
int arrayIndex = value / 64;
int length = value - arrayIndex * 64;
array[arrayIndex] &= ~((ulong)1 << (length - 1));
}
}测试
C#
[MemoryDiagnoser]
public partial class Test
{
[GlobalSetup]
public void Startup(){}
FindPoerTest t = new FindPoerTest();
[Benchmark]
public void FindIP()
{
t.Find(t.array, out byte point);
}
[Benchmark]
public void AddIP()
{
t.Add(t.array, 253);
}
[Benchmark]
public void DeleteIP()
{
t.Delete(t.array, 253);
}
}基准
C#
BenchmarkDotNet=v0.13.5, OS=Windows 10 (10.0.19045.3208/22H2/2022Update)
AMD Ryzen 3 2200G with Radeon Vega Graphics, 1 CPU, 4 logical and 4 physical cores
.NET SDK=7.0.100
[Host] : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2 [AttachedDebugger]
DefaultJob : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2
| Method | Mean | Error | StdDev | Median | Allocated |
|--------- |---------:|----------:|----------:|---------:|----------:|
| FindIP | 8.246 ns | 0.1799 ns | 0.1595 ns | 8.303 ns | - |
| AddIP | 4.604 ns | 0.2598 ns | 0.7067 ns | 4.923 ns | - |
| DeleteIP | 4.837 ns | 0.1308 ns | 0.1701 ns | 4.873 ns | - |