UVA1590 IP Networks题目大意给定若干 32 位 IP 地址IP 采用点分十进制形式分为 4 个字节每个字节取值 0‑255。需要求出可以容纳全部这些 IP 地址的最小 IP 网络。一个 IP 网络由网络地址和子网掩码共同描述二者同样为 32 位点分十进制。子网掩码二进制特点是高位全部为 1低位全部为 0网络地址由 IP 地址与子网掩码做按位与运算得到。掩码中 0 的位数 n 决定网络大小该网络一共有 2ⁿ个 IP 地址n 越小网络越小。最终输出这个最小网络的网络地址与子网掩码。输入多组测试用例。每组第一行整数 m1 ≤ m ≤1000代表 IP 数量接下来 m 行每行一个 IP 地址同一个 IP 可以重复出现。输出每组输出两行第一行网络地址点分十进制第二行子网掩码点分十进制解题思路程序读取多组测试用例每组先读取 IP 数量将点分十进制格式的 IP 地址转换为 32 位长整型数字接着从最高位向最低位逐位比对全部 IP统计所有 IP 公共一致的高位位数利用预先生成的掩码表得到对应子网掩码将首个 IP 与掩码按位与运算得到网络地址最后把网络地址和子网掩码还原回点分十进制格式输出。完整代码importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;classIpUtil{publicstaticfinallong[]MASK_TABLEnewlong[33];static{for(intbits0;bits32;bits){if(bits0){MASK_TABLE[bits]0L;}elseif(bits32){MASK_TABLE[bits]0xFFFFFFFFL;}else{MASK_TABLE[bits](0xFFFFFFFFL(32-bits))0xFFFFFFFFL;}}}publicstaticlongipToLong(StringipStr){String[]partsipStr.split(\\.);longres0;for(inti0;i4;i){intvalInteger.parseInt(parts[i]);res(res8)|val;}returnres0xFFFFFFFFL;}publicstaticStringlongToIp(longnum){StringBuildersbnewStringBuilder();for(inti3;i0;i--){intshifti*8;longbyteVal(numshift)0xFFL;sb.append(byteVal);if(i!0)sb.append(.);}returnsb.toString();}}publicclassIPNetworks{publicstaticListLongreadInput(Scannersc){ListLongipLongListnewArrayList();intmsc.nextInt();sc.nextLine();for(inti0;im;i){Stringlinesc.nextLine().trim();longipValIpUtil.ipToLong(line);ipLongList.add(ipVal);}returnipLongList;}publicstaticlong[]processData(ListLongipList){intcommonBits32;longfirstipList.get(0);for(intbitPos31;bitPos0;bitPos--){intbit0(int)(firstbitPos)1;booleanallSametrue;for(longip:ipList){intcurrBit(int)(ipbitPos)1;if(currBit!bit0){allSamefalse;break;}}if(!allSame){commonBits31-bitPos;break;}}longmaskIpUtil.MASK_TABLE[commonBits];longnetworkAddrfirstmask;returnnewlong[]{networkAddr,mask};}publicstaticvoidprintResult(long[]result){StringnetIpIpUtil.longToIp(result[0]);StringmaskIpIpUtil.longToIp(result[1]);System.out.println(netIp);System.out.println(maskIp);}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);while(sc.hasNext()){ListLongipsreadInput(sc);long[]ansprocessData(ips);printResult(ans);}sc.close();}}测评结果
