Function bit_ceil 

fn bit_ceil(x: u64) -> u64

Examples found in repository

crates/competitive/src/tree/static_top_tree.rs (line 196)

    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
        let n = graph.vertices_size();
        assert!(n > 0);
        assert!(root < n);
        assert_eq!(graph.edges_size() + 1, n);

        let RootedInfo {
            order,
            children_start,
            children,
            edge_child,
            parent_edge,
        } = rooted_children(graph, root);
        let mut this = Self {
            root,
            n,
            edge_child,
            parent_edge,
            compressed: Vec::with_capacity(n.saturating_sub(1)),
            raked: Vec::with_capacity(n.saturating_sub(1)),
            vertex_links: vec![
                VertexLinks {
                    heavy_parent: usize::MAX,
                    compress_parent: usize::MAX,
                    rake_parent: usize::MAX,
                };
                n
            ],
            compress_roots: vec![None; n],
            rake_roots: vec![None; n],
        };

        let mut heavy_child = vec![usize::MAX; n];
        let mut mask = vec![1u64; n];
        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());

        for &u in order.iter().rev() {
            let children = &children[children_start[u]..children_start[u + 1]];
            let mut sum_rake = 0u64;
            for &v in children {
                sum_rake += bit_ceil(mask[v]) << 1;
            }
            mask[u] = bit_ceil(sum_rake);
            for &v in children {
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                let step = 1u64 << depth;
                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
                if cand <= mask[u] {
                    mask[u] = cand;
                    heavy_child[u] = v;
                }
            }

            let mut has = 0u64;
            let mut num_light = 0usize;
            for &v in children {
                if v == heavy_child[u] {
                    continue;
                }
                num_light += 1;
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                this.build_compress(v, &heavy_child, &mask);
                buckets[depth].push(Node {
                    depth,
                    slot: Slot::RakeLeaf(v),
                });
                has |= 1u64 << depth;
            }
            if num_light == 0 {
                continue;
            }

            while num_light > 1 {
                let left = pop_bucket(&mut buckets, &mut has);
                let right = pop_bucket(&mut buckets, &mut has);
                let node = this.merge_rake(left, right);
                let depth = node.depth;
                buckets[depth].push(node);
                has |= 1u64 << depth;
                num_light -= 1;
            }

            let root = pop_bucket(&mut buckets, &mut has);
            this.rake_roots[u] = Some(root.slot);
            for &v0 in children {
                if v0 == heavy_child[u] {
                    continue;
                }
                let rake_parent = this.vertex_links[v0].rake_parent;
                let mut v = v0;
                while v != usize::MAX {
                    this.vertex_links[v].heavy_parent = u;
                    this.vertex_links[v].rake_parent = rake_parent;
                    v = heavy_child[v];
                }
            }
        }

        this.build_compress(root, &heavy_child, &mask);
        this
    }

    pub fn vertices_size(&self) -> usize {
        self.n
    }

    pub fn edges_size(&self) -> usize {
        self.edge_child.len()
    }

    pub fn dp<C>(
        &self,
        vertices: Vec<<C as Cluster>::Vertex>,
        edges: Vec<<C as Cluster>::Edge>,
    ) -> StaticTopTreeDp<'_, C>
    where
        C: Cluster,
    {
        StaticTopTreeDp::new(self, vertices, edges)
    }

    pub fn fold_all<C>(
        &self,
        vertices: &[<C as Cluster>::Vertex],
        edges: &[<C as Cluster>::Edge],
    ) -> <C as Cluster>::Point
    where
        C: Cluster,
    {
        assert_eq!(vertices.len(), self.vertices_size());
        assert_eq!(edges.len(), self.edges_size());
        let path = self.fold_compress::<C>(
            vertices,
            edges,
            self.compress_roots[self.root].expect("root compress tree must exist"),
        );
        C::add_edge(&path)
    }

    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
        let start = vertex;
        let mut stack = Vec::new();
        while vertex != usize::MAX {
            stack.push(Node {
                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
                slot: Slot::CompressLeaf(vertex),
            });
            loop {
                let len = stack.len();
                if len >= 3
                    && (stack[len - 3].depth == stack[len - 2].depth
                        || stack[len - 3].depth <= stack[len - 1].depth)
                {
                    let tail = stack.pop().unwrap();
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    let node = self.merge_compress(left, right);
                    stack.push(node);
                    stack.push(tail);
                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    stack.push(self.merge_compress(left, right));
                } else {
                    break;
                }
            }
            vertex = heavy_child[vertex];
        }
        while stack.len() > 1 {
            let right = stack.pop().unwrap();
            let left = stack.pop().unwrap();
            stack.push(self.merge_compress(left, right));
        }
        let root = stack.pop().unwrap();
        self.compress_roots[start] = Some(root.slot);
        root
    }